POJ 2115 C Looooops：線性同餘方程求最小正整數解

題目轉化

給定 a, b, c, k，求最小正整數 x 滿足：

c * x ≡ b - a (mod 2^k)

即解線性同餘方程 a'x ≡ b' (mod n)，其中 a'=c、b'=b-a、n=2^k。

數學基礎：擴展歐幾里得算法

方程 ax ≡ b (mod n) 有解 ⇔ d = gcd(a, n) 整除 b。
若 d = ax₁ + ny（由擴展歐幾里得得 x₁），則一特解為：

x₀ = x₁ * (b/d) (mod n)

通解為 x = x₀ + t*(n/d)，最小正整數解在 [0, n/d) 區間內。

證明摘要

1. d = gcd(a, n) ⇒ ∃x₁,y: d = ax₁ + ny
2. 兩邊模 n：d ≡ ax₁ (mod n)
3. b = kd ⇒ b ≡ kd ≡ kax₁ ≡ a(kx₁) (mod n)
4. 故 x = kx₁ = x₁*(b/d) 為一解。

C++ 完整實作

#include <iostream>
using namespace std;
#define L long long

L Egcd(L a, L b, L &x, L &y) { // 擴展歐幾里得
    if (b == 0) { x = 1; y = 0; return a; }
    L d = Egcd(b, a % b, x, y);
    L tp = x; x = y; y = tp - (a / b) * y;
    return d;
}

void MLE(L a, L b, L n) { // 解模線性方程
    L x, y, d = Egcd(a, n, x, y);
    if (b % d == 0) {
        L x0 = (b / d * x) % n + n; // 確保非負
        cout << x0 % (n / d) << endl; // 最小正解在 n/d 範圍內
    } else {
        cout << "FOREVER" << endl; // 無解
    }
}

int main() {
    L a, b, c; int k;
    while (cin >> a >> b >> c >> k) {
        if (!a && !b && !c && !k) break;
        MLE(c, b - a, 1LL << k);
    }
    return 0;
}

樣本驗證

關鍵技巧

• 使用 1LL << k 計算 2^k 避免溢位。
• x0 % (n/d) 直接取得最小正解（群論：解集合形成 d 個等價類，每類週期 n/d）。
• 擴展歐幾里得遞迴實作簡潔高效。