【2024.9.28练习】青蛙的约会

题目描述

---

题目分析

        由于两只青蛙都在跳跃导致变量多，不妨采用物理题中的相对运动思想，设青蛙A不动，青蛙B每次跳米，两只青蛙的距离为米。正常来说，只要模拟青蛙B与青蛙A的相对运动过程，最终当青蛙B与青蛙A距离为0时即可求得总跳跃次数。但是难点在于数据量大，按部就班的模拟将会超时。

        由于这是一道有关整数和环的数学题，考虑使用扩展欧几里得算法求解。现直接假设一只青蛙静止，另一只青蛙每次位移为，总跳跃次数为，一圈长度为，跳跃的圈数为，青蛙间的距离为。则题目满足方程：。显然要使方程有整数解，必须满足的条件是：必须是  和  的最大公约数的倍数，即。这可以通过贝祖定理证明。

        接下来的难点是求出最小跳跃次数。根据拓展欧几里得算法已经得到了方程的一组特解，但这不一定是最优解，根据线性同余方程的通解公式：

只需让该特解模除即可求出跳跃次数在间的最小正整数解。

        提交后有一处测试点有误，经检查，原来在exgcd算法中，如果两个参数存在负数，输出的最大公因数也可能是负数。这并不影响所得特解的正确性，但在求最小正解的时候，需要采取措施让取模后的结果转变为正数。

---

我的代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;// 扩展欧几里得算法
ll extgcd(ll a, ll b, ll& x, ll& y) {if (b == 0) {x = 1;y = 0;return a;}ll d = extgcd(b, a % b, y, x);y -= (a / b) * x;return d;
}int main() {ll x, y, m, n, L;cin >> x >> y >> m >> n >> L;ll a = n - m;  // 移项后得到 a = n - mll b = x - y;  // 常数项 b = x - yll l = L;      // 模数为 Lll x0, y0;ll d = extgcd(a, l, x0, y0);  // 使用扩展欧几里得求解if (b % d != 0) {cout << "Impossible" << endl;}else {// 存在解的情况，求最小非负整数解ll k = (x0 * (b / d)) % (l / d); //其中x0*(b/d)为一个方程的特解if (k < 0) {if (l / d > 0) {k += l / d;  // 保证 k 为非负}else {k -= l / d;  // 保证 k 为非负}}cout << k << endl;}return 0;
}

由于扩展欧几里得算法参数使用了引用，导致逻辑相对更难理解，我利用原本欧几里得算法的数学递推逻辑修改为一下函数，程序可以成功运行：

ll x_0;
ll y_0;
ll x_1;
ll y_1;
ll extgcd(ll a, ll b) {ll d = a;if (b != 0) {d = extgcd(b, a % b);x_0 = y_1;y_0 = x_1 - a / b * y_1;y_1 = y_0;x_1 = x_0;}else {x_1 = 1;y_1 = 0;}return d;
}