「Bzoj 1477」青蛙的约会 (扩展欧几里得算法解不定方程)

BZOJ 1477
luogu免权限地址
扩展欧几里得算法，由题可列$(x+m*t)\equiv (y+n*t)\pmod L$，其中$t$为所求
由同余性质得：$(x+m*t)-(y+n*t)=Lk$
变形得：$(n-m)t+lk=x-y$，则转换为$ax+by=c$的形式

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL x, y, m, n, L; 
LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b);}
LL abss(LL a) {return a >= 0 ? a : -a;}
void exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, x, y);
    int tmp = x;
    x = y, y = tmp - a / b * y;
}
void clean() {}
void solve() {
    clean();
    LL xi = m - n, yi = L, c = y - x, g = gcd(xi, yi);
    if (c % g != 0) {printf("Impossible\n"); return ;}
    c /= g, xi /= g, yi /= g;
    LL a, b;
    exgcd(xi, yi, a, b);
    yi = abss(yi);
    a = ((a * c) % yi + yi) % yi;
    printf("%lld\n", a);
}
int main() {
    scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L), solve();
    return 0;
}