POJ 1061青蛙的约会

青蛙的约会

exgcd
 1 #include<cstdio>
 2 #include<iostream>
 3 #define LL long long
 4 using namespace std;
 5 
 6 LL x,y,n,m,l;
 7 
 8 LL exgcd(LL a,LL b,LL &x,LL &y)
 9 {
10     if(b==0) { x=1; y=0; return a;}
11     LL r=exgcd(b,a%b,x,y);
12     LL t=x; x=y; y=t-a/b*y; 
13     return r;
14 }
15 
16 int main()
17 {
18     cin>>x>>y>>m>>n>>l;
19     LL xx,yy,c,g,a;
20     a=m-n; c=y-x; g=exgcd(m-n,l,xx,yy);
21     if(c%g!=0)
22     {
23         printf("Impossible");
24         return 0;
25     }
26     xx=c/g*xx; l/=g;
27     if(l<0) l=-l;
28     xx=(xx%l+l)%l;
29     printf("%lld",xx);
30 }
View Code