【题目描述】
原题来自：NEFU 84
大圣在佛祖的手掌中。
我们假设佛祖的手掌是一个圆圈，圆圈的长为 n，逆时针记为：0,1,2,⋯,n−1，而大圣每次飞的距离为 d。现在大圣所在的位置记为 x，而大圣想去的地方在 y。要你告诉大圣至少要飞多少次才能到达目的地。
【输入】
有多组测试数据。
第一行是一个正整数 T，表示测试数据的组数；
每组测试数据包括一行，四个非负整数，分别为如来手掌圆圈的长度 n，筋斗所能飞的距离 d，大圣的初始位置 x 和大圣想去的地方 y。
注意孙悟空的筋斗云只沿着逆时针方向翻。
【输出】
对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。如果无论翻多少个筋斗云也不能到达，输出Impossible。
【输入样例】
2 3 2 0 2 3 2 0 1【输出样例】
1 2【提示】
数据范围与提示：
对于全部数据，2<n<10^9,0<d<n,0≤x,y<n。
1. 题意转换
扒掉题目这层《西游记》的外衣，这道题本质上是在求：给定同余方程 x+k⋅d≡y (mod n)，求满足条件的最小非负整数解 k。这就是一个最标准的一元一次同余方程（线性同余方程），其核心解法模型正是扩展欧几里得算法（exgcd）。
2. 思考过程与解题思路
第一直觉的暴力解法： 直觉上，我们可以写一个
while循环，让大圣一步步飞：每次位置变为(当前位置 + d) % n，用一个计数器记录飞的次数，直到遇见目标位置 y 为止。为什么会超时？看看数据范围：n<10^9。如果 n 极大而 d=1，大圣在最坏情况下需要飞 10^9 次才能到达目标！一秒钟 C++ 大约能跑 10^8 次运算，遇到多组测试数据（T）的轰炸，这种一步步模拟的暴力解法绝对会超时。推导正解的破局之路： 既然不能一步步飞，我们就必须用数学方法对时间进行“降维打击”。
大圣飞了 k 步后，实际走过的总距离是 k⋅d。
因为手掌是个长度为 n 的圆圈，这意味着走过 n 的倍数就会回到原点。所以目标位置满足：x+k⋅d=y+p⋅n （p 是大圣在这个过程中绕过的完整圈数，是个未知的整数）。
我们把已知量放一边，未知量放一边，移项变形：
d⋅k−n⋅p=y−x
仔细观察这个式子，它完美匹配了裴蜀定理的标准形式：A⋅x0+B⋅y0=C。 在这里，我们已知 A=d,B=−n,C=y−x，要求的是未知数 k（大圣飞的次数，即公式里的 x0）。这就顺理成章地引出了终极武器——扩展欧几里得（exgcd）。
3. 算法设计与样例推演
核心算法：利用
exgcd(a, b, x, y)求出方程 a⋅x+b⋅y=gcd(a,b) 的基础特解，然后将解等比例放大，最后在合法的周期内将解转为最小非负整数。核心推导等式：
目标方程：d⋅x0+n⋅y0=y−x
扩欧求解：d⋅x′+n⋅y′=gcd(d,n)
放大倍数：times=(y−x)/gcd(d,n)
真实步数：x0=x′⋅times
局部周期：mod=n/gcd(d,n)
极简数据手玩推演（带入样例 2：
3 2 0 1）： 输入：n=3,d=2,x=0,y=1。算常数：C=y−x=1−0=1。
调用扩欧：
exgcd(2, 3, x0, y0)。求出 2⋅x0+3⋅y0=gcd(2,3)=1 的解。算出 d=1，基础解 x0=−1,y0=1 （验证：2×(−1)+3×1=1）。判断有无解：常数 C=1 能被 gcd=1 整除，有解！
算放大倍数：times=1/1=1。
算局部周期：mod=n/d=3/1=3。
黄金转正：真实步数 x0=−1×1=−1。由于步数不能是负数，我们要加上周期转正：((−1(mod 3))+3)(mod 3)=2。得出结果：大圣需要飞 2 次。与样例输出完美吻合！
4. 时空复杂度分析
时间复杂度：O(Tlog(min(n,d)))。对于每组测试数据，算法的核心开销全部在
exgcd递归函数上。欧几里得算法的复杂度是对数级别的，即使 n 达到 10^9，单次求解最多只需几十次递归，在 1s 的时限内极其宽裕，跑满所有数据耗时几乎为 0 ms。空间复杂度：O(1)。递归调用的栈空间深度不超过几十层，仅用到几个基础变量存储状态，空间开销微乎其微。
5. 坑点与易错总结
数据范围带来的溢出黑洞：虽然题目说 n<10^9 可以用
int存下，但是别忘了我们在算真实步数时执行了x0 * times。x0 和 times 都可能高达 10^9，两者相乘瞬间达到 10^18！这里如果用int存x0，会溢出变成负数爆零。标程中非常机智地把x0设为了long long，成功化解了暗雷。右侧常数可能为负：题目中目标 y 完全可能小于起点 x（大圣往回飞的假象），导致 y−x<0。C++ 中负数除法和取模带有特例性质。标程中的
x0 = ((x0 * times % mod) + mod) % mod;这个“黄金转正句型”就是为了抹平一切负数取模带来的隐患，必须肌肉记忆般地背下来。周期必须除以最大公约数：很多初学者在最后取模时，会习惯性直接对着 n 取模。但根据数论性质，方程两边同除以 gcd 后，合法的循环周期也会缩小为 n/gcd。标程中的
long long mod = n / dd;是极其关键的一步。
6. 标程
//单纯的扩欧 //问题可以转化为x+d*x0≡y (mod n) //问题可以转化为d*x0+n*y0=y-x #include <iostream> using namespace std; int t; //扩展欧几里得 long long exgcd(int a,int b,long long &x_,long long &y_){ if(b==0){ x_=1; y_=0; return a; } long long d=exgcd(b,a%b,x_,y_); long long tmp=x_; x_=y_; y_=tmp-(a/b)*y_; return d; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>t; while(t--){ int n,d,x,y; cin>>n>>d>>x>>y; long long x0,y0; //扩欧求出基础方程d*x0+n*y0= gcd(d,n) 的特解 dd接收gcd long long dd=exgcd(d,n,x0,y0); //根据裴蜀定理 如果y-x不能被gcd整除 无解 if((y-x)%dd!=0) cout<<"Impossible"<<endl; //如果有解 else{ //算出缩放倍数 因为exgcd求出的是d*x0+n*y0=dd的情况 //所以需要算出实际方程常数相比基础方程常数放大了多少倍 int times=(y-x)/dd; //算出新的模数 //等式同除以gcd后 周期必须同步缩小 long long mod=n/dd; //1 x0*times等比例放大求出所需步数（可能为负数或极大值） //2 对mod取模进行压缩 //3 +mod然后再%mod 避免负数取模产生的未定义行为 让答案变成最小正整数 x0=((x0*times%mod)+mod)%mod; cout<<x0<<endl; } } return 0; }
