链接：

http://poj.org/problem?id=2115

题意：

给出a,b,c,k，问从a开始 每次+c，加多少次能变成b，结果模2^k

题解：

计算cx 同余 (b-a)(mod2^k)即可

代码：

31 ll extgcd(ll a, ll b, ll &x, ll &y) { 32 ll d = a; 33 if (b) { 34 d = extgcd(b, a%b, y, x); 35 y -= (a / b)*x; 36 } 37 else x = 1, y = 0; 38 return d; 39 } 40 41 ll line_mod_equation(ll a, ll b, ll n) { 42 ll x, y; 43 ll d = extgcd(a, n, x, y); 44 if (b%d == 0) { 45 x = x*(b / d) % (n / d); 46 if (x < 0) x += n / d; 47 return x; 48 } 49 return -1; 50 } 51 52 int main() { 53 ios::sync_with_stdio(false), cin.tie(0); 54 ll a, b, c, k; 55 while (cin >> a >> b >> c >> k) { 56 if (!a && !b && !c && !k) break; 57 k = 1LL << k; 58 ll ans = line_mod_equation(c, b - a, k); 59 if (ans == -1) cout << "FOREVER" << endl; 60 else cout << ans << endl; 61 } 62 return 0; 63 }