题解 | #青蛙的约会#

【青蛙的约会】

设跳了$tt$​​次后两个青蛙相遇，即$x+(m\times t)\equiv y+(n\times t)(\mathrm{m}\mathrm{o}\mathrm{d}L)x+(m\backslash times\; t)\backslash equiv\; y\; +\; (n\backslash times\; t)(\backslash mod\; L)$。

方程可以转换成$(m-n)\times t+L\times u=(y-x)(m-n)\backslash times\; t\; +\; L\backslash times\; u=(y-x)$。

根据裴蜀定理，可知方程$ax+by=max+by=m$有整数解时当且仅当$mm$是$aa$及$bb$的最大公约数$d=\gcd (a,b)d=\backslash gcd(a,b)$​的倍数。

可以把无解的情况特判掉。

用扩展欧几里得定理可以求出原方程的通解，又因为题目要求第一次碰面，所以要求出$tt$​​的一个最小正整数解。

详细的可以看oi-wiki，线性同余方程https://oi-wiki.org/math/number-theory/linear-equation/。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int x2, y2;
    int res = exgcd(b, a % b, x2, y2);
    x = y2;
    y = x2 - a / b * y2;
    return res;
}

int x, y, m, n, L;
int t, u, d;
int c;

signed main() {
    cin >> x >> y >> m >> n >> L;

    if (m - n > 0) {
        d = exgcd(m - n, L, t, u);
        c = y - x;
    } else {
        d = exgcd(n - m, L, t, u);
        c = x - y;
    }
    if ((y - x) % d) {
        cout << "Impossible";
        return 0;
    }
    t = t * c / d;
    cout << (t % (L / d) + (L / d)) % (L / d);

    return 0;
}