传送门：POJ 2115 - C Looooops

题目大意：

给你一个 $C$语言中的 $for$ 循环伪代码，如下：

1
2
for (variable = A; variable != B; variable += C)
    statements;

varibale是变量名，所有数据的类型都是一个 $k$ 位的无符号整数，给你 $A,B,C,k$ 的值，问你要这个循环会执行多少次后退出。

解题思路：

我们知道在 $C$语言中，如果一个数超过了它的上界，那么会从下界重新开始，同样如果超过了下界也是一样会从上界重新开始。
比如说，int类型的范围是 $[-2147483648,2147483647]$。有如下代码：

1
2
int int_max = 2147483647;
cout << int_max + 1 << endl;

输出如下：

1
-2147483648

可以看出数值从上界超出后回到了下界，这样这道题就很好去算了，设循环会执行 $x$ 次，我们可以根据题意列出一个等式：
$(A+Cx)\%2^k=B$
变形一下成为我们需要的形式：
$Cx+2^ky=B-A$
这里 $y$ 的值不重要，就是表示一下 $2^k$ 的倍数使等式成立。
我们需要的是 $x$，因为循环次数肯定是非负的，所以我们要去计算这个等式的 $x$ 解的最小的非负解。
分析到这里，这个题就很明显了，是一个扩展欧几里得求解二元一次方程的板子题，然后在把 $x$ 算一下最小非负的值就搞定了。
然后就是解方程的时候如果发现没有整数解，那就是 FOREVER 的情况了。

通过代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll q = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return q;
}
bool eqa_solve(ll &x, ll &y, ll a, ll b, ll c)
{
    ll q = exgcd(a, b, x, y);
    if (c % q != 0)
        return false;
    ll tms = c / q;
    x *= tms;
    y *= tms;
    ll m = b / q;
    x = (x % m + m) % m; // 这句就是把 x 变为最小的非负整数解
    return true;
}
int main(void)
{
    ll a, b, c, k;
    while (cin >> a >> b >> c >> k && k)
    {
        ll x, y, m = (ll)1 << k;
        if (eqa_solve(x, y, c, m, b - a))
            cout << x << endl;
        else
            cout << "FOREVER" << endl;
    }
    return 0;
}