Description
Sample Input
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
Sample Output
0
2
32766
FOREVER
题解：
这题和poj1067是一个解题思路，首先把方程列出来，设要循环x次才能终止，x=(B-A+2^k)%2^k/C,得Cx+2^k*y=B-A
1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstdio> 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 }
原文：http://www.cnblogs.com/Beckinsale/p/7439863.html
