[LgP1516]青蛙的约会

OI 题解 数论 数学

算法：数论

设相遇时间为$t$，那么，两只青蛙相遇可以表示为$x+mt\equiv y+nt(\bmod l)$，即$x+mt-y-nt=kl$，化简得$(m-n)t+lk=y-x$。
扩欧解即可。

代码

#include<cstdio>
#include<algorithm>
using std::swap;
typedef long long ll;
void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
    if (!b) {
        d = a; x = 1; y = 0;
    } else {
        exgcd(b, a%b, d, y, x);
        y -= (a/b)*x;
    }
}
int main() {
    ll x, y, m, n, l;
    scanf("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &l);
    ll t, k, d;
    if(n > m) {
        swap(m, n);
        swap(x, y);
    }
    exgcd(m-n, l, d, t, k);
    if((y-x) % d) printf("Impossible\n");
    else {
        printf("%lld\n", (t*(y-x)/d + (l/d)) % (l/d));//调整t为最小正值。
    }
    return 0;
}