只是简单地exgcd求解，要注意的是k位存储系统意思是当 i 大于2^k时从头开始计算
1 #include2 #include 3 using namespace std; 4 long long A,B,C,k,x1,y1,a,b,e,d; 5 long long exgcd(long long a,long long b) 6 { 7 long long tmp; 8 if(b==0) 9 {10 x1=1;y1=0;11 return a;12 }13 d=exgcd(b,a%b);14 tmp=x1;15 x1=y1;16 y1=tmp-a/b*x1;17 return d;18 }19 int main()20 {21 long long c[34];22 c[0]=1;23 for(int i=1;i<34;i++)24 c[i]=c[i-1]*2;25 while(~scanf("%lld%lld%lld%lld",&A,&B,&C,&k))26 {27 if(A==0&&B==0&&C==0&&k==0)28 break;29 a=C;30 b=c[k];31 e=B-A;32 d=exgcd(a,b);33 if(e%d!=0)34 {35 printf("FOREVER\n");36 continue;37 }38 x1=e/d*x1;39 b=b/d;40 if(b<0)41 b=-b;42 x1=x1%b;43 if(x1<0)44 x1=x1+b;45 printf("%lld\n",x1);46 }47 return 0;48 }
