POJ1061青蛙的约会

 1 #include <iostream>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include<string>
 5 #include<cstring>
 6 #define LL long long
 7 using namespace std;
 8 
 9 LL a,b,x,y,d;
10 
11 LL gcd(LL a,LL b)
12 {
13     if(b==0) return a;
14     else return gcd(b,a%b);
15 }
16 void ex_gcd(LL a,LL b,LL &x,LL &y,LL &d)
17 {
18     LL t;
19     if(b==0){
20         d=a,x=1,y=0;
21     }
22     else{
23         ex_gcd(b,a%b,x,y,d);
24         t=x,x=y,y=t-a/b*y;
25     }
26 }
27 int main()
28 {
29     LL p,q,m,n,L;
30     cin>>p>>q>>m>>n>>L;
31     a=m-n,b=q-p;
32 
33     if(a<0) a=-a,b=-b;
34     LL Gcd=gcd(a,L);
35 
36     if(b%Gcd!=0) cout<<"Impossible"<<endl;
37     else{
38         LL temp;
39         a=a/Gcd,temp=L/Gcd,b=b/Gcd;
40         ex_gcd(a,temp,x,y,d);
41         b=b*x;
42 
43         b%=L;
44         if(b<0) cout<<b+L<<endl;
45         else cout<<b<<endl;
46     }
47 
48 
49     return 0;
50 }