信息学奥赛一本通在线题库 青蛙的约会

思路：
有题目可以得出(mt + x) mod L = (nt + y) mod L，这样才可以相遇，因为比如1 mod 2 = (1 + 2 * n) mod 2，所以就有了(mt + x) + k * L = (nt + y)转之后就有了(m - n) * t + k * L = y - x，我们可以将之看成ax + by = c，从而使用扩展欧几里德定理。
由扩展欧几里德定理可以得出x, y, gcd(a, b)的值，由于欧几里德的公式是ax + by = gcd(a, b)，但是本题需要求的是ax + by = c, 所以就有了 (ax + by) * c / gcd = gcd * c / gcd; 所以就要x * c / gcd，而且x的通解是x +k * b / gcd,所以就要取模b / gcd才能得到最小x， 而且得出的x有怕是负数，所以就有了x = (x % (b / gcd) + b / gcd) % (b / gcd);

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll Exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll r = Exgcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return r;
}
int main() {
    ll x, y, m, n, l;
    scanf("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &l);
    ll a = m - n;
    ll b = l;
    ll c = y - x;
    if (a < 0) {
        a = -a;
        c = -c;
     }
    ll gcd = Exgcd(a, b, x, y);
    if (c % gcd != 0) printf("Impossible");
    else {
        x = x * c / gcd;
        b /= gcd;
        x = (x % b + b) % b;
        printf("%lld", x);
    }
    return 0;
}