【题目描述】原题来自POJ 1061两只青蛙在网上相识了它们聊得很开心于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上于是它们约定各自朝西跳直到碰面为止。可是它们出发之前忘记了一件很重要的事情既没有问清楚对方的特征也没有约定见面的具体位置。不过青蛙们都是很乐观的它们觉得只要一直朝着某个方向跳下去总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙你被要求写一个程序来判断这两只青蛙是否能够碰面会在什么时候碰面。我们把这两只青蛙分别叫做青蛙 A 和青蛙 B 并且规定纬度线上东经 0 度处为原点由东往西为正方向单位长度 1 米这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 x 青蛙 B 的出发点坐标是 y 。青蛙 A 一次能跳 m 米青蛙 B 一次能跳 n 米两只青蛙跳一次所花费的时间相同。纬度线总长 L 米。现在要你求出它们跳了几次以后才会碰面。【输入】输入只包括一行 5 个整数 x,y,m,n,L 。【输出】输出碰面所需要的跳跃次数如果永远不可能碰面则输出一行 Impossible 。【输入样例】1 2 3 4 5【输出样例】4【提示】数据范围与提示对于 100% 的数据 0≤x,y2×10^9,0m,n2×10^9,0L2×10^9。 保证 x≠y。1. 题意转换一句话剥离背景题目描述了两只青蛙在周长为L的环形数轴上同向跳跃要求它们相遇的具体步数。本质数学模型这本质上是在求解一个一元线性同余方程的最小正整数解。用数学语言翻译就是已知起点 x,y步长 m,n 和模数 L求满足 (xk⋅m)≡(yk⋅n) (modL) 的最小非负整数 k。未来如果我们把两个角色扩展到N个角色求相遇这就直接变成了扩展中国剩余定理的核心基石。2. 思考过程与解题思路面对这道题第一直觉的暴力解法是什么 很多初学者看到“跳跃直到碰面”第一反应自然是写一个while循环来模拟每次让 A 和 B 各自加上步长再对 L 取模用一个计数器记录跳跃次数直到坐标相等为止。为什么会 TLE看看数据范围L2×10^9。如果两只青蛙刚好在跳了 10^9 步后相遇你的while循环就要跑 10^9 次直接导致超时。所以纯模拟是一条死路。如何一步步推导到正解既然不能模拟我们就把青蛙的运动轨迹写成代数式。 假设它们跳了 k 次后相遇 青蛙 A 的坐标是xk⋅m 青蛙 B 的坐标是yk⋅n 由于它们在一个周长为 L 的圆周数轴上坐标相同意味着两者的绝对距离之差是圆周长 L 的整数倍。 于是可以列出等式(xk⋅m)−(yk⋅n)p⋅L(p为某个整数)我们把未知数 k跳跃次数和 p相差圈数留在等号左边常数移到右边(m−n)⋅k−L⋅py−x为了符合标准的代数形式我们令 am−nbLcy−x方程就变成了极其经典的二元一次不定方程a⋅kb⋅p′c注这里把 −p 视作另一个整数 p′正负号在求解整数解时并无本质影响。 看到 axbyc破局的终极武器就浮出水面了——扩展欧几里得算法exgcd。3. 算法设计与样例推演算法设计明确系数令,,。我们要解方程。符号净化因为m可能小于n导致a是负数而exgcd算法底层遇到负数取模会崩溃。所以当 a0时必须将等式两边同乘-1强行转正。同时目标c也要用(c%LL)%L转为正数。判定无解算出如果c不能被d整除说明永远无法相遇根据裴蜀定理直接输出Impossible。等比放大与取模求最小正整数解将 exgcd 求出的基础解k放大c/d倍。注意此时解的真实循环周期已经从L缩小成了L/d。必须对着L/d取模才能精准提纯出最小正整数解。样例推演手玩数据输入样例1 2 3 4 5x1, y2, m3, n4, L5计算系数a 3-4 -1, b 5, c 2-1 1。净化负数a -1 0变号得 a 1, c -1。接着把c强行转正。呼叫扩欧解。得出特解k 1。计算倍数与新周期放大倍数是。真实周期是。终极转正答案 ((4 * 1) % 5 5) % 5 4。与样例输出完美一致4. 时空复杂度分析时间复杂度核心运算只有一次exgcd函数调用。扩展欧几里得算法的时间复杂度是对数级别的即 O(log(min(∣a∣,∣b∣)))。在本题数据范围内最多递归约 30 多层耗时在纳秒级时间复杂度记为 O(logL)远远低于 O(1s) 的时限。空间复杂度由于只开了几个全局变量并且递归层数极浅空间复杂度为 O(1)或计入栈空间为 O(logL)绝对不会引发 MLE。5. 坑点与易错总结爆int危机开long long本题输入数据虽然在 2×10^9 以内但在做移项减法比如 y−x、或者后续计算(c/d*k)时乘法会产生高达 1018 级别的中间值如果不用long long可能溢出导致 WA。系数a为负数的陷阱在推导式子 (m−n)k 时m 完全可能小于 n导致 a0。如果不处理直接扔进exgcd由于 C 负数取模的特性得出的结果会产生偏差。正解是在 a0 时把方程两端同时变号a−a,c−c。C负数取模机制不管求出来的答案是正是负一定要用ans (ans % mod mod) % mod的黄金句型包裹起来否则遇到负坐标直接爆零。当 c 是负数时c % L在 C 中依然是负数。必须使用通用的正数化取模公式c (c % L L) % L。通解转化为最小正整数解exgcd 求出的只是其中一组特解而题目要求解的是“最小跳跃次数最小正整数”。所以最终结果必须对步长周期取模模数为modL/gcd(a,b)答案归一化公式为(k%modmod)%mod。周期缩放定律最核心坑点为什么代码最后一行是%(l/d)而不是%l因为当你在等式两边除以最大公约数d时状态空间发生了“降维”。这个世界里有效的落脚点只剩下 l/d个所以它的真实循环周期必须同步压缩为 l/d。不对新周期取模你就永远拿不到“最小正整数解”。6. 标程详解//这道题青蛙A的坐标为(13*k)%5 //青蛙B的坐标为24*k)%5 //当两个青蛙坐标相同时就是碰面的时候 //所以这类题第一步写出同余式 第二步移项进行exgcd 第三步确保无负数 //这道题其实正是扩展中国剩余定理的基石 目前这道题是找两只青蛙跳几次碰面 //如果变成n只青蛙跳几次以后才会碰面 就变成了彻底的扩展中国剩余定理 #include iostream using namespace std; long long x,y,m,n,l; long long k,p; //求解a*x_b*y_gcd(a,b)的一组特解(x_, y_)并返回最大公约数d long long exgcd(long long a,long long b,long long x_,long long y_){ //递归边界当b为0时gcd(a,0)a //此时方程变为a*x_a显然x_1,y_0即可 if(b0){ x_1; y_0; return a; } //递归向下求解注意此处b和a%b换位 long long dexgcd(b,a%b,x_,y_); //回溯时根据下一层的x_(x1)和y_(y1)推导本层的x_和y_ //数学推导xy1,yx1-(a/b)*y1 long long tmpx_; x_y_; y_tmp-(a/b)*y_; return d; } int main(){ long long d0; cinxymnl; //这道题先写出同余式xm*k≡yn*k (mod l) //然后移项 (m-n)*k≡y-x (mod l) //转化为等式 m-n)*kp*ly-x //这个时候这个式子就变成了axbyc的形式了就可以用扩展欧几里得去求了 //此时的exgcd(a,b,x_,y_) am-n,bl x_k y_p cy-x //a b需要大于0 long long am-n; long long bl; long long cy-x; //如果a(即m-n)是负数我们将方程两边同时变号 //这样保证放入exgcd的a始终是非负数避免c负数取模产生问题 if(a0){ a-a; c-c; } //c经过运算后可能是负数 利用下面这行代码将其拉回[0,l-1]的正数区间 c(c%ll)%l; //调用exgcd求解a*kb*pgcd(a,b) //此时的k和p是对等号右边为gcd(a,b)时的特解 dexgcd(a,b,k,p); //裴蜀定理判定如果目标常数c不能被gcd(a,b)整除 则方程无整数解 if(c%d!0) coutImpossible; //等比放大与提取最小正整数解 //1.(c/d)*k - 这是真实需要的步数等比例放大特解 //2.l/d - 这是等式约分后 缩小形成的新模数真实的循环周期 //3.对(l/d)取模并转正 确保得到的是第一次相遇的最小非负步数 else cout((c/d*k)%(l/d)l/d)%(l/d); return 0; }