分析

设每次大圣起点为$a$，终点为$b$，一次能跳距离为$d$，环形总长度为$n$，最大公因数为$gcd$
根据题意本题的方程为：
$$ a+dx\equiv b(\bmod n) $$
进一步变换得：
$$ dx\equiv (b-a)(\bmod n) $$
即使用扩展欧几里得求解方程：
$$ dx+ny=(b-a) $$

解得特解$$ x_{0},y_{0} $$
$$ x=x_{0}+k\frac{n}{gcd} $$
$$ y=y_{0}+k\frac{d}{gcd} $$

之后判断(b-a)是否为gcd的倍数，不是则说明无解，输出$Impossible$
否则，将得到的x扩大(b-a)/gcd倍，然后输出其最小正整数解。

C++ 代码

#include<bits/stdc++.h>
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;
    }
    LL d = exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int T;
int main()
{
    cin>>T;
    while(T--)
    {
        LL n,d,a,b,x,y;
        cin>>n>>d>>a>>b;
        LL gcd=exgcd(d,n,x,y);
        if((b-a)%gcd){  
            puts("Impossible");
        }
        else{
            x*=(b-a)/gcd;   //将得到的x扩大(b-a)/gcd倍
            LL t=abs(n/gcd);    
            cout<<(x%t+t)%t<<endl;  //输出最小整数解
        }
    }
    return 0;
}