poj 2115 C Looooops

扩展的欧几里得算法……
 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cmath>
 6 #include<iomanip>
 7 #include<string>
 8 using namespace std;
 9 __int64 extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
10 {
11     __int64 d;
12     if(b==0)
13     {
14         x=1;
15         y=0;
16         return a;
17     }
18     else
19     {
20         d=extend_gcd(b,a%b,x,y);
21         __int64 temp=x;
22         x=y;
23         y=temp-a/b*y;
24     }
25     return d;
26 }
27 int main()
28 {
29     __int64 x,y,ans,m,n,l,i,a,b,k,c;
30     scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l);
31         k=n-m;c=x-y;
32         if(k<0)
33         {
34             k=-k;
35             c=-c;
36         }
37         i=extend_gcd(k,l,a,b);
38         if((x-y)%i)
39             cout<<"Impossible
"<<endl;
40         else 
41         {
42             ans=(c)/i*a%l+l;
43             ans=(ans)%(l/i);
44             printf("%I64d
",ans);
45         }
46     return 0;
47 }
View Code