POJ-1061 青蛙的约会

传送门

括欧题

注意，若<x,y>是

　　ax+by=c

的一组解。

定义

　　d=gcd(a,b),

那么

　　<x-b/d,y+a/d>

也是方程的一组解。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

LL extgcd(LL a, LL b, LL& x, LL& y) {
    LL d = a;
    if (b) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

LL x, y, m, n, L;

int main() {    
    scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L);
    if (m == n) {
        puts("Impossible");
    } else {
        LL c = y - x;
        LL a, k;
        LL d = extgcd(m - n + L, L, a, k);
        if (c % d == 0) {
            LL M = L / d;
            LL ans = ((a * (c / d)) % M + M) % M; 
            printf("%lld
", ans);
        } else {
            puts("Impossible");
        }
    }
    
    return 0;
}