POJ 2115 C Looooops - 擴展歐幾里得算法求解同餘方程

問題背景

給定 while 循環 while(x=a; x!=b; x+=c) statement;，在模 2^k 意義下，statement 會被執行多少次？

等價於求解同餘方程：a + c * x ≡ b (mod 2^k)，即 c * x ≡ (b - a) (mod 2^k)。

解法：擴展歐幾里得算法

設 g = gcd(c, 2^k)。方程有解當且僅當 g | (b - a)。若有解，利用擴展歐幾里得算法求出 c * x + 2^k * y = g 的一組解 (x0, y0)，則原方程的一組解為 x = x0 * (b - a) / g。最小非負解為 x mod (2^k / g)。

代碼實現（C++）

#include 
using namespace std;
typedef long long LL;

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

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;
        LL A = c, B = -mod, C = b - a;
        LL d, x, y;
        exgcd(A, B, d, x, y);
        if (C % d != 0) {
            cout << "FOREVER" << endl;
        } else {
            x = x * (C / d);
            LL mod2 = mod / d;
            x = (x % mod2 + mod2) % mod2;
            cout << x << endl;
        }
    }
    return 0;
}

關鍵點總結

• 將循環次數問題轉化為線性同餘方程求解。
• 擴展歐幾里得算法求解 ax + by = gcd(a,b)。
• 注意模數為 2^k，使用位運算 1LL << k 計算。
• 無解時輸出 "FOREVER"。