题意分析

题目给出一个C语言风格的for循环：

for (variable = A; variable != B; variable += C)
    statement;

循环开始时将变量$variable$初始化为$A$，每次循环后$variable$增加$C$，直到$variable$等于$B$时停止。所有运算在$k$位无符号整数下进行，即模$2^k$运算。我们需要计算循环体$statement$的执行次数，如果循环不会终止则输出$FOREVER$。

解题思路

1. 问题转化：循环的执行次数$n$满足以下同余方程：

   $$A + n \cdot C \equiv B \pmod{2^k}$$

   可以转化为：

   $$n \cdot C \equiv B - A \pmod{2^k}$$

   这是一个线性同余方程，形式为：

   $$a \cdot x \equiv c \pmod{b}$$

   其中$a = C$，$b = 2^k$，$c = B - A$。

2. 线性同余方程求解：线性同余方程$a \cdot x \equiv c \pmod{b}$有解的条件是$c$能被$a$和$b$的最大公约数$d$整除。即：

   $$d = \gcd(a, b), \quad d \mid c$$

   如果$d \nmid c$，则方程无解，循环不会终止，输出$FOREVER$。

3. 扩展欧几里得算法：用扩展欧几里得算法求解方程$a \cdot x + b \cdot y = d$，得到特解$x_0$。然后方程的通解为：

   $$x = x_0 \cdot \frac{c}{d} + k \cdot \frac{b}{d}$$

   最小正整数解为：

   $$x_{\text{min}} = \left( x_0 \cdot \frac{c}{d} \bmod \frac{b}{d} + \frac{b}{d} \right) \bmod \frac{b}{d} $$

4. 实现步骤：

   • 计算$d = \gcd(C, 2^k)$。
   • 检查$(B - A)$是否能被$d$整除。
   • 如果能整除，用扩展欧几里得算法求解并输出最小正整数解；否则输出$FOREVER$。

标程

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

ll A, B, C, a, b, c, k, ans;

void exgcd(ll a, ll b, ll &x, ll &y, ll &d) {
    if (!b) {
        x = 1;
        y = 0;
        d = a;
    } else {
        exgcd(b, a % b, y, x, d);
        y -= x * (a / b);
    }
}

int main() {
    while (cin >> A >> B >> C >> k) {
        if (A == 0 && B == 0 && C == 0 && k == 0) break;
        
        a = C;
        b = 1LL << k;
        c = B - A;
        
        ll x, y, d;
        exgcd(a, b, x, y, d);
        
        if (c % d == 0) {
            ans = (c / d * x % (b / d) + b / d) % (b / d);
            cout << ans << endl;
        } else {
            puts("FOREVER");
        }
    }
    return 0;
}