题目链接：
http://acm.pku.edu.cn/JudgeOnline/problem?id=2115 本题是一道数论的入门题，模型为求 ax = b (mod n)，本题中，a = C, b = B-A, n = 2^k
因此使用求解模线性方程算法modular_linear。关于算法的详细原理可参见
欧几里德_扩展欧几里德_模线性方程，这篇blog对相关的算法给出了详细的证明，推荐。
下面给出本题的代码，本题有几点需要注意：
1.需要使用64位整数计算，因为2^32对普通整数会溢出；
2.第48行，在求n时，因为在C++中，默认0x01为int型，如果不加强制转换，那么移位后会溢出；所以强制类型转换是必须的。
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