poj 2115

题目链接 http://poj.org/problem?id=2115

题目意思就解这样一个同余方程 A+CX≡B（mod）M 这里 M = 1<<k 跟上一篇的做法差不多。用扩展欧几里得做

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <stack>
 5 #include <queue>
 6 #include <map>
 7 #include <algorithm>
 8 #include <vector>
 9 
10 using namespace std;
11 
12 const int maxn = 1000005;
13 
14 typedef long long LL;
15 
16 LL ex_gcd(LL a,LL b,LL &x,LL &y)
17 {
18    if(b == 0){
19         x = 1;
20         y = 0;
21         return a;
22    }
23    LL r = ex_gcd(b,a%b,x,y);
24    LL t = x;
25       x = y;
26       y = t - a/b*y;
27       return r;
28 }
29 int main()
30 {
31     LL i,ans,a,b,c,d,k,x,y;
32     while(cin>>a>>b>>c>>k&&a+b+c+k){
33       LL tmp = c;
34            c = b - a;
35            a = tmp;
36            b = (LL)1 << k;
37            LL d = ex_gcd(a,b,x,y);
38            if(c%d!=0){
39             printf("FOREVER
");
40            }
41            else{
42             ans = x*c/d;
43             LL t = b/d;
44             ans = ((ans%t)+t)%t;
45             printf("%lld
",ans);
46            }
47 
48     }
49     return 0;
50 }

View Code