1640：C Looooops

题目描述

对于 C 语言的

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

循环语句，问在 $k$ 位存储系统中循环几次才会结束。若在有限次内结束，则输出循环次数。否则输出死循环。

输入格式

多组数据，每组数据一行四个整数 $A, B, C, k$。$k$ 表示 $k$ 位存储系统。

读入以 0 0 0 0 结束。

输出格式

若在有限次内结束，则输出循环次数。否则输出 FOREVER。

样例

样例输入 #1

3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0

样例输出 #1

0
2
32766
FOREVER

样例解释 #1

第一组：$A=3, B=3, C=2, k=16$。初始值 $A=B$，所以循环次数为 $0$（因为一开始就满足 variable == B，不执行循环体）。输出 $0$。

第二组：$A=3, B=7, C=2, k=16$。在 $16$ 位存储系统中，整数范围为 $0$ 到 $2^{16}-1 = 65535$，且是模 $2^{16}$ 的运算。循环条件 variable != B，每次增加 $C=2$。相当于解方程 $A + C \cdot t \equiv B \pmod{2^k}$，求最小非负整数 $t$。方程：$3 + 2t \equiv 7 \pmod{65536}$，即 $2t \equiv 4 \pmod{65536}$。解得 $t=2$（因为 $2 \times 2 = 4$）。输出 $2$。

第三组：$A=7, B=3, C=2, k=16$。方程：$7 + 2t \equiv 3 \pmod{65536}$，即 $2t \equiv -4 \equiv 65532 \pmod{65536}$。注意 $-4 \bmod 65536 = 65532$。方程 $2t \equiv 65532 \pmod{65536}$。由于 $\gcd(2,65536)=2$，且 $65532$ 能被 $2$ 整除，有解。化简为 $t \equiv 32766 \pmod{32768}$。最小非负解 $t=32766$。输出 $32766$。

第四组：$A=3, B=4, C=2, k=16$。方程：$3 + 2t \equiv 4 \pmod{65536}$，即 $2t \equiv 1 \pmod{65536}$。由于 $\gcd(2,65536)=2$，$1$ 不能被 $2$ 整除，无解。所以死循环，输出 FOREVER。

数据范围

对于全部数据：

• $1 \le k \le 32$
• $0 \le A, B, C < 2^k$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题是求解线性同余方程。设循环次数为 $t$，则经过 $t$ 次循环后，变量值为 $A + C \cdot t$（在 $k$ 位存储系统中，整数运算是模 $2^k$ 的）。循环结束条件是 $A + C \cdot t \equiv B \pmod{2^k}$，即

令 $a = C$，$b = B - A$，$n = 2^k$，则方程为 $a t \equiv b \pmod{n}$。

求解步骤：

1. 计算 $d = \gcd(a, n)$。
2. 如果 $b$ 不能被 $d$ 整除，则无解，输出 FOREVER。
3. 否则，方程两边同除以 $d$，得到 $a' t \equiv b' \pmod{n'}$，其中 $a' = a/d$，$b' = b/d$，$n' = n/d$。
4. 由于 $\gcd(a', n') = 1$，用扩展欧几里得算法求 $a'$ 在模 $n'$ 下的逆元 $inv$，则 $t \equiv b' \cdot inv \pmod{n'}$。
5. 最小非负整数解为 $t = (b' \cdot inv \bmod n' + n') \bmod n'$。

注意：$n = 2^k$ 可能很大（$k$ 最大 $32$，$n = 2^{32} = 4294967296$），但 $a, b$ 也在 $[0, 2^k)$ 范围内。计算 $\gcd$ 和扩展欧几里得时用 long long（64 位）即可。

特殊情形：

• 如果 $A == B$，则 $t=0$，直接输出 $0$（因为一开始就相等，循环次数为 $0$）。
• 如果 $C == 0$，则每次增加 $0$，变量不变。如果 $A == B$，则 $t=0$；否则永远无法等于 $B$，死循环。

另外，注意 $b = B - A$ 可能为负数，需要调整到模 $n$ 意义下的非负剩余：$b = (B - A + n) \bmod n$。但直接计算 $b = B - A$，然后在同余方程中处理负数（扩展欧几里得算法允许负数）。

多组数据，直到输入 0 0 0 0 结束。