【题目描述】原题来自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【提示】数据范围与提示对于全部数据2n10^9,0dn,0≤x,yn。1. 题意转换扒掉题目这层《西游记》的外衣这道题本质上是在求给定同余方程 xk⋅d≡y (mod n)求满足条件的最小非负整数解 k。这就是一个最标准的一元一次同余方程线性同余方程其核心解法模型正是扩展欧几里得算法exgcd。2. 思考过程与解题思路第一直觉的暴力解法 直觉上我们可以写一个while循环让大圣一步步飞每次位置变为(当前位置 d) % n用一个计数器记录飞的次数直到遇见目标位置 y 为止。为什么会超时看看数据范围n10^9。如果 n 极大而 d1大圣在最坏情况下需要飞 10^9 次才能到达目标一秒钟 C 大约能跑 10^8 次运算遇到多组测试数据T的轰炸这种一步步模拟的暴力解法绝对会超时。推导正解的破局之路 既然不能一步步飞我们就必须用数学方法对时间进行“降维打击”。大圣飞了 k 步后实际走过的总距离是 k⋅d。因为手掌是个长度为 n 的圆圈这意味着走过 n 的倍数就会回到原点。所以目标位置满足xk⋅dyp⋅n p 是大圣在这个过程中绕过的完整圈数是个未知的整数。我们把已知量放一边未知量放一边移项变形d⋅k−n⋅py−x仔细观察这个式子它完美匹配了裴蜀定理的标准形式A⋅x0​B⋅y0​C。 在这里我们已知 Ad,B−n,Cy−x要求的是未知数 k大圣飞的次数即公式里的 x0​。这就顺理成章地引出了终极武器——扩展欧几里得exgcd。3. 算法设计与样例推演核心算法利用exgcd(a, b, x, y)求出方程 a⋅xb⋅ygcd(a,b) 的基础特解然后将解等比例放大最后在合法的周期内将解转为最小非负整数。核心推导等式目标方程d⋅x0​n⋅y0​y−x扩欧求解d⋅x′n⋅y′gcd(d,n)放大倍数times(y−x)/gcd(d,n)真实步数x0​x′⋅times局部周期modn/gcd(d,n)极简数据手玩推演带入样例 23 2 0 1 输入n3,d2,x0,y1。算常数Cy−x1−01。调用扩欧exgcd(2, 3, x0, y0)。求出 2⋅x0​3⋅y0​gcd(2,3)1 的解。算出 d1基础解 x0​−1,y0​1 验证2×(−1)3×11。判断有无解常数 C1 能被 gcd1 整除有解算放大倍数times1/11。算局部周期modn/d3/13。黄金转正真实步数 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. 坑点与易错总结数据范围带来的溢出黑洞虽然题目说 n10^9 可以用int存下但是别忘了我们在算真实步数时执行了x0 * times。x0​ 和 times 都可能高达 10^9两者相乘瞬间达到 10^18这里如果用int存x0会溢出变成负数爆零。标程中非常机智地把x0设为了long long成功化解了暗雷。右侧常数可能为负题目中目标 y 完全可能小于起点 x大圣往回飞的假象导致 y−x0。C 中负数除法和取模带有特例性质。标程中的x0 ((x0 * times % mod) mod) % mod;这个“黄金转正句型”就是为了抹平一切负数取模带来的隐患必须肌肉记忆般地背下来。周期必须除以最大公约数很多初学者在最后取模时会习惯性直接对着 n 取模。但根据数论性质方程两边同除以 gcd 后合法的循环周期也会缩小为 n/gcd。标程中的long long mod n / dd;是极其关键的一步。6. 标程//单纯的扩欧 //问题可以转化为xd*x0≡y (mod n) //问题可以转化为d*x0n*y0y-x #include iostream using namespace std; int t; //扩展欧几里得 long long exgcd(int a,int b,long long x_,long long y_){ if(b0){ x_1; y_0; return a; } long long dexgcd(b,a%b,x_,y_); long long tmpx_; x_y_; y_tmp-(a/b)*y_; return d; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cint; while(t--){ int n,d,x,y; cinndxy; long long x0,y0; //扩欧求出基础方程d*x0n*y0 gcd(d,n) 的特解 dd接收gcd long long ddexgcd(d,n,x0,y0); //根据裴蜀定理 如果y-x不能被gcd整除 无解 if((y-x)%dd!0) coutImpossibleendl; //如果有解 else{ //算出缩放倍数 因为exgcd求出的是d*x0n*y0dd的情况 //所以需要算出实际方程常数相比基础方程常数放大了多少倍 int times(y-x)/dd; //算出新的模数 //等式同除以gcd后 周期必须同步缩小 long long modn/dd; //1 x0*times等比例放大求出所需步数可能为负数或极大值 //2 对mod取模进行压缩 //3 mod然后再%mod 避免负数取模产生的未定义行为 让答案变成最小正整数 x0((x0*times%mod)mod)%mod; coutx0endl; } } return 0; }