形式化题目

在 $k$ 位无符号存储系统（$1 \leqslant k \leqslant 32$）中，所有运算结果对 $2^k$ 取模（高位截断）。变量从 $A$ 出发，每轮执行一次自增 $C$，即第 $t$ 轮后的值为 $A + tC \bmod 2^k$。问最少执行多少轮后变量第一次等于 $B$；若永远取不到 $B$，输出 FOREVER。

多组数据，每组一行四个整数 $A, B, C, k$（$0 \leqslant A, B, C < 2^k$），以 0 0 0 0 结束。

样例解释（以第四组 3 4 2 16 为例，变量每轮加 2，奇偶性不变，永远到不了偶数 4）：

值始终为奇数，与 $B = 4$（偶数）永不相遇 → FOREVER。

正解

思路

朴素做法：直接模拟，变量从 $A$ 开始每次加 $C$ 模 $2^k$，数步数。但步数最多可达 $2^k / \gcd(C, 2^k)$——$k = 32$、$C$ 为奇数时约 $4.3 \times 10^9$ 步，1 秒时限内不可能完成；判死循环还得先找到循环节，同样要 $O(2^k)$。瓶颈在于"一步一步走"没有利用加法运算的周期性。

优化推导：把"第 $t$ 轮后第一次等于 $B$"翻译成同余条件：

这是一个标准的线性同余方程，循环次数就是它的最小非负整数解 $t$（$t = 0$ 对应 $A = B$，“一次都不执行”，天然统一）。用扩展欧几里得求解，设 $M = 2^k$，$g = \gcd(C, M)$：

1. 有解判定：方程有解当且仅当 $g \mid (B - A)$。理由：$Ct$ 在模 $g$ 意义下恒为 $0$，所以右边必须也是 $g$ 的倍数。无解即序列永远不经过 $B$ → 输出 FOREVER。

2. 求最小解：有解时，由扩展欧几里得得一组 $(x, y)$ 满足 $Cx + My = g$。两边同乘 $\frac{B-A}{g}$ 得 $C \cdot \left(x \cdot \frac{B-A}{g}\right) \equiv B - A \pmod M$，所以 $t_0 = x \cdot \frac{B-A}{g}$ 是一个特解。同余方程的全部解在模 $\frac{M}{g}$ 意义下唯一（两个解之差能被 $\frac{M}{g}$ 整除），故最小非负解为

   $$t = x \cdot \frac{B-A}{g} \bmod \frac{M}{g}.$$

用样例 3 7 2 16 走一遍求解链（方程 $2t \equiv 4 \pmod{65536}$）：

1
2
3g = gcd(2, 65536) = 2，g | 4          → 有解
扩展欧几里得：2·1 + 65536·0 = 2       → x = 1
t = 1 · (4/2) mod (65536/2) = 2       → 输出 2

而 7 3 2 16 时 $2t \equiv -4$，$t = 1 \cdot (-2) \bmod 32768 = 32766$，即变量绕 $\frac{65536}{2} = 32768$ 个奇数一圈后从上方逼近 3，与样例输出一致。

实现要点：Python 大整数无中间乘法溢出问题（C++ 需用 long long 并小心 $x \cdot \frac{B-A}{g}$ 的量级）；递归版扩展欧几里得深度 $O(k) \leqslant 32$ 层，安全；读入用 zip(it, it, it, it) 每次消费一行四个整数，遇 0 0 0 0 停止。

代码

Python 版：

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
40
41#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 23:35
# update_at: 2026-09-30 23:35

import sys


def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    """返回 (g, x, y) 满足 a*x + b*y = g = gcd(a, b)。"""
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y


def loop_times(a: int, b: int, c: int, k: int) -> str:
    """k 位系统里循环几次到达 B：解同余方程 c*t ≡ B-A (mod 2^k) 的最小非负 t。"""
    mod = 1 << k
    g, x, _ = ext_gcd(c, mod)   # c 在 mod 下的逆相关系数
    diff = b - a
    if diff % g:
        return "FOREVER"        # gcd 不整除差值 → 无解 → 死循环
    period = mod // g           # 解在模 period 意义下唯一
    return str(x * (diff // g) % period)


def solve() -> None:
    nums = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    for a, b, c, k in zip(nums, nums, nums, nums):  # 同一迭代器 zip 四次 = 每次取一行四个数
        if a == b == c == k == 0:
            break
        out.append(loop_times(a, b, c, k))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
40
41
42
43
44
45
46
47
48
49/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:12
 * update_at: 2026-10-06 00:12
 */
#include <iostream>
using namespace std;
typedef long long ll;

// 扩展欧几里得：求 g = gcd(a, b)，并给出 x, y 使 a*x + b*y = g
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

int main() {
    ll a, b, c, k;
    while (cin >> a >> b >> c >> k) {
        if (a == 0 && b == 0 && c == 0 && k == 0) {
            break;
        }
        ll mod = 1LL << k; // k 位系统的模数 2^k
        ll x, y;
        ll g = ext_gcd(c, mod, x, y); // g = gcd(C, 2^k)
        ll diff = b - a;              // 同余方程右端 Ct ≡ B - A (mod 2^k)
        if (diff % g != 0) {
            cout << "FOREVER" << "\n"; // gcd 不整除差值，永远到不了 B
            continue;
        }
        ll period = mod / g; // 解在模 period 意义下唯一
        // 把 x、diff/g 都化到 [0, period)，再用 __int128 相乘防止溢出
        x = ((x % period) + period) % period;
        ll factor = ((diff / g) % period + period) % period;
        __int128 prod = (__int128)x * factor;
        ll ans = prod % period; // 最小非负解
        cout << ans << "\n";
    }
    return 0;
}

复杂度

每组数据一次扩展欧几里得，时间 $O(\log 2^k) = O(k)$，递归栈空间 $O(k)$。设数据组数为 $T$，总时间 $O(T \log 2^k)$，与标准 C++ 正解同阶。

总结

• 关键转化：$k$ 位系统里的"循环几次到达 $B$"= 线性同余方程 $Ct \equiv B - A \pmod{2^k}$ 的最小非负解，无解即死循环。
• 求解套路：扩展欧几里得求 $g = \gcd(C, 2^k)$ 与系数 $x$；$g \nmid (B-A)$ 输出 FOREVER，否则答案为 $x \cdot \frac{B-A}{g} \bmod \frac{2^k}{g}$。
• 边界自检：$A = B$ 得 $0$；$C = 0$ 时 $g = 2^k$，$A = B$ 输出 $0$、否则 FOREVER，与"变量不动"的语义一致。