poj2115 C Looooops

思路：

求最小的非负整数t使得C * t % 2^k = (B - A) % 2^k。

实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 ll abs(ll x)
 8 {
 9     return x < 0 ? -x : x;
10 }
11 
12 ll extgcd(ll a, ll b, ll & x, ll & y)
13 {
14     int d = a;
15     if (!b)
16     {
17         x = 1; y = 0;
18     }
19     else
20     {
21         d = extgcd(b, a % b, y, x);
22         y -= (a / b) * x;
23     }
24     return d;
25 }
26 
27 int main()
28 {
29     ll a, b, c, k;
30     while (cin >> a >> b >> c >> k, a || b || c || k)
31     {
32         ll tmp = 1;
33         tmp <<= k;
34         ll d, x, y;
35         d = extgcd(c, tmp, x, y);
36         if ((b - a) % d) puts("FOREVER");
37         else
38         {
39             ll mod = abs(tmp / d);
40             x = (x * (b - a) / d % mod + mod) % mod;
41             cout << x << endl;
42         }
43     }
44     return 0;
45 }