poj2115--CLooooops--扩展欧几里得

 1 #include
 2 #include
 3 #include
 4 #include
 5 #define ll long long
 6 using namespace std;
 7 ll exgcd(ll a,ll b,ll &x,ll &y)
 8 {
 9     if(b==0){x=1;y=0;return a;}
10     ll t=exgcd(b,a%b,x,y);
11     ll tmp=x;x=y;
12     y=tmp-a/b*y;
13     return t;
14 }
15 int main()
16 {
17     ll A,B,C,k,x,y;
18     while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k)!=EOF)
19     {
20         if(A+B+C+k==0)break;
21         ll n=1ll<<k;
22         ll d=exgcd(C,n,x,y);
23         ll r=n/d;
24         if((B-A)%d)printf("FOREVER\n");
25         else
26         {
27             ll ans=((B-A)/d*x%r+r)%r;
28             printf("%lld\n",ans);
29         }
30     }
31     return 0;
32 }