題目鏈接：
http://acm.pku.edu.cn/JudgeOnline/problem?id=2115 本題是一道數(shù)論的入門題，模型為求 ax = b (mod n)，本題中，a = C, b = B-A, n = 2^k
因此使用求解模線性方程算法modular_linear。關(guān)于算法的詳細(xì)原理可參見
歐幾里德_擴(kuò)展歐幾里德_模線性方程，這篇blog對(duì)相關(guān)的算法給出了詳細(xì)的證明，推薦。
下面給出本題的代碼，本題有幾點(diǎn)需要注意：
1.需要使用64位整數(shù)計(jì)算，因?yàn)?^32對(duì)普通整數(shù)會(huì)溢出；
2.第48行，在求n時(shí)，因?yàn)樵贑++中，默認(rèn)0x01為int型，如果不加強(qiáng)制轉(zhuǎn)換，那么移位后會(huì)溢出；所以強(qiáng)制類型轉(zhuǎn)換是必須的。
1 #include <cstdio>
2 typedef long long Int64;
3
4 // ax + by = d 其中d = gcd(a,b)
5 Int64 extend_euclid(Int64 a, Int64 b, Int64& x, Int64& y)
6 {
7 if(b == 0)
8 {
9 x = 1;
10 y = 0;
11 return a;
12 }
13 else
14 {
15 Int64 gcd, t;
16 gcd = extend_euclid(b, a%b, x, y);
17
18 t = x;
19 x = y;
20 y = t - a / b * y;
21 return gcd;
22 }
23 }
24
25 // ax = b mod n
26 Int64 modular_linear(Int64 a, Int64 b, Int64 n)
27 {
28 Int64 x = 0;
29 Int64 y = 0;
30 Int64 d = 0;
31
32 d = extend_euclid(a,n,x,y);
33
34 if(b % d == 0)
35 {
36 x = (x * (b / d)) % n + n;
37 return x % (n/d);
38 }
39 return -1;
40 }
41
42 int main()
43 {
44 Int64 A,B,C,k;
45
46 while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k),k)
47 {
48 Int64 n = (Int64)0x01 << k;
49
50 Int64 res = modular_linear(C, B-A, n);
51 if(res == -1)
52 {
53 printf("FOREVER\n");
54 }
55 else
56 {
57 printf("%lld\n",res);
58 }
59 }
60
61 return 0;
62 }
63