POJ 1061 扩展欧几里得

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 typedef long long ll;
 5 
 6 void gcd(ll a,ll b,ll& d,ll& x,ll& y){
 7     if(b==0){
 8         d=a; x=1; y=0; return ;
 9     }
10     gcd(b,a%b,d,y,x);
11     y-=(a/b)*x;
12 }
13 
14 int main(){
15     ll x,y,m,n,l;
16     while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)){
17         ll a=n-m,b=l, c=x-y,d,xx,yy;
18         gcd(a,b,d,xx,yy);
19         if(c%d==0){
20             xx*=c/d;
21             if(xx>0){
22                 xx%=b;
23             }
24             else{
25                     xx=(xx+b)%b;                 // xx<0的情况
26             }
27             printf("%lld
",xx);
28         }
29         else{
30             puts("Impossible");
31         }
32     }
33 }