引理

1.裴蜀定理
2.扩展欧几里得定理
(详见分享)

题解:

分析:
1.由题,设需要翻ans个筋斗,需要重复长度为n的圆圈m次,则可以得到等式:$ans \times d=n \times m+(y-x)$
将等式变形,得$m \times n-ans \times d=x-y$
显然,这里我们要求的是ans和m两个变量,由裴蜀定理可知,当且仅当x-y是gcd(n,d)的倍数时ans和m有通解,显然这就要用到和裴蜀定理绑定的扩展欧几里得定理,令a=m,b=-ans,求得$a \times n+b \times d=gcd(n,d)$的一组通解,然后两边同乘(x-y)/gcd(n,d)转为上式.当然题目所求的是最小正数解。
2.关于求最小正数解:b=b’+k(n/gcd(n,d)),这里b’为扩展欧几里得定理求出的一组特殊解,我们也可以用求正余数的方法直接求解：n/=gcd(n,d),b=(b%n+n)%n(求正模)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b){
        x=1;
        y=0;
        return a;
    }
    int gcd=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return gcd;
}

int main()
{
    int t;
    while(cin >> t){
        ll n,d,x,y;
        while(t--){
            ll a,b;
            scanf("%lld %lld %lld %lld\n",&n,&d,&x,&y);
            ll gcd=exgcd(n,d,a,b);
            if((y-x)%gcd){ //不能整除
                printf("Impossible\n");
            }
            else{
                b*=(y-x)/gcd;
                n/=gcd;
                printf("%lld\n",(b%n+n)%n);
            }
        }
    }
    return 0;
}