[数据结构与算法]AcWing 222. 青蛙的约会

#include <bits/stdc++.h>
// #define LOCAL
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int z = x;
    x = y;
    y = z - y * (a / b);
    return d;
}

signed main()
{
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    IOS;
    int x, y, m, n, l, k, t;
    cin >> x >> y >> m >> n >> l;
    int d = exgcd(n - m, l, k, t);
    if ((x - y) % d)
    {
        cout << "Impossible\n";
        return 0;
    }
    int ansk = (x - y) / d * k;
    int mod = abs(l / d);
    ansk = (ansk % mod + mod) % mod;
    cout << ansk << '\n';
}

这里有一个要注意的地方,当我们乘除混用防止溢出时,要时刻关注能否被整除