括欧题

注意，若<x,y>是

　　ax+by=c

的一组解。

定义

　　d=gcd(a,b),

那么

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

也是方程的一组解。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         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\n", ans);        } else {            puts("Impossible");        }    }        return 0;}