青蛙的约会

AcWing-222-青蛙的约会

实现

#include <iostream>
using namespace std;

typedef long long LL;
LL a, b, m, n, L;
LL x, y;

LL exgcd (LL a, LL b, LL& x, LL& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, x, y);
    LL copy_x = x, copy_y = y;
    x = copy_y, y = copy_x - copy_y * (a / b);
    return d;
}

int main () {
    cin >> a >> b >> m >> n >> L;

    LL d = exgcd(m - n, L, x, y), t = abs(L / d);
    if ((b - a) % d == 0) {
        cout << ((x * (b - a) / d) % t + t) % t << endl;
    } else {
        cout << "Impossible" << endl;
    }
    return 0;
}