poj--2115 C Looooops

只是简单地exgcd求解，要注意的是k位存储系统意思是当 i 大于2^k时从头开始计算

 1 #include <iostream>
 2 #include<cstdio>
 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
");
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
",x1);
46     }
47     return 0;
48 }

View Code