POJ 2115 简单的模线性方程求解

简单的扩展欧几里得题

这里 2^k 不能自作聪明的用 1<<k来写， k >= 31时就爆int了，即使定义为long long 也不能直接这样写

后来老老实实 for(int i=1 ; i<=k ; i++) bb = bb*2; 才过了= =

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 #define ll long long
 6 ll ex_gcd(ll a , ll &x , ll b , ll &y)
 7 {
 8     if(b == 0){
 9         x = 1 , y = 0;
10         return a;
11     }
12     ll ans = ex_gcd(b , x , a%b , y);
13     int t = x;
14     x = y , y = t - a/b*y;
15     return ans;
16 }
17 int main()
18 {
19    // freopen("a.in" , "r" , stdin);
20     int a , b , c , k;
21     while(scanf("%d%d%d%d" , &a , &b , &c , &k)){
22         if(a == 0 && b == 0 && c == 0 && k == 0) break;
23         ll aa = c , bb = 1 , cc = b-a , x , y;
24         for(int i=1 ; i<=k ; i++) bb = bb*2;
25         ll g = ex_gcd(aa , x , bb , y);
26         if(cc % g != 0){
27             puts("FOREVER");
28             continue;
29         }
30         ll kk = cc / g;
31         x*=kk , y*=kk;
32         aa/=g , bb/=g;
33         if(x >= 0)
34             x = x - x/bb*bb;
35         else
36             x = x - x/bb*bb+bb;
37         printf("%I64d
" , x);
38     }
39     return 0;
40 }