POJ 1061 青蛙約會：擴展歐幾里得算法求解線性同餘方程完整解析

一、問題數學建模

兩隻青蛙初始位置 x, y，每次跳躍 m, n 米，軌道長度 L (環狀)。求最小非負整數 S 使：

(x + S*m) % L == (y + S*n) % L

移項得：S*(n - m) ≡ (x - y) (mod L)

設 a = n - m, b = L, c = x - y，求解線性同餘方程：

a*S ≡ c (mod b)

二、擴展歐幾里得算法核心

求解 a*x + b*y = gcd(a,b) 的整數解。遞迴關係：

// 回傳 gcd(a,b)，並設定 x,y 使 a*x + b*y = gcd
long long exgcd(long long a, long long b, long long *x, long long *y) {
    if (b == 0) { *x = 1; *y = 0; return a; }
    long long x1, y1;
    long long g = exgcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return g;
}

三、線性同餘方程求解步驟

1. 計算 d = gcd(a, b)。
2. 若 c % d != 0 → 無解，輸出 Impossible。
3. 縮約：a' = a/d, b' = b/d, c' = c/d，此時 gcd(a', b') = 1。
4. 用擴展歐幾里得求 a'*x0 + b'*y0 = 1。
5. 原方程一組解：S0 = c' * x0。
6. 通解：S = S0 + k*b' (k ∈ Z)。
7. 最小非負解：S = (S0 % b' + b') % b'。

四、完整 AC 程式碼 (C/C++)

#include 
#include 

typedef long long LL;

LL exgcd(LL a, LL b, LL *x, LL *y) {
    if (b == 0) { *x = 1; *y = 0; return a; }
    LL x1, y1;
    LL g = exgcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return g;
}

int main() {
    LL x, y, m, n, L;
    while (scanf("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &L) == 5) {
        LL a = n - m;
        LL b = L;
        LL c = x - y;
        
        LL x0, y0;
        LL d = exgcd(a, b, &x0, &y0); // a*x0 + b*y0 = d
        
        if (c % d != 0) {
            puts("Impossible");
            continue;
        }
        
        LL mod = b / d;
        // 通解: S = (c/d)*x0 + k*(b/d)
        LL S = (c / d) * x0;
        S %= mod;
        if (S < 0) S += mod;
        printf("%lld\n", S);
    }
    return 0;
}

五、關鍵細節與避坑

1. 負數模運算：C/C++ % 可能為負，必須 (x%mod+mod)%mod 修正。
2. 長長整數：L < 2.1e9，中間運算 a*x0 可能超過 32 位，必須用 long long (64 位)。
3. a = n - m 可能為負：exgcd 需處理負數，或取絕對值後調整符號。上述實作直接支援負數 a。
4. k=0 解：若 x == y 初始重疊，c=0，解 S=0 (但題目 x≠y)。
5. 多組測試資料：while(scanf(...)==5) 讀到 EOF。

六、數學原理證明補充

線性同餘方程 ax ≡ c (mod b) 有解 ⇔ gcd(a,b) | c。
若 x0 是 ax ≡ 1 (mod b/d) 的解 (即 a'*x0 ≡ 1 (mod b'))，則 c'*x0 是 a'*x ≡ c' (mod b') 的解。
通解為 x = c'*x0 + k*b'，最小非負解即為答案。

七、延伸應用

• 中國剩餘定理 (CRT) 多同餘方程組求解。
• RSA 解密指數 d = e^{-1} mod φ(n) 計算模逆元。
• 遊戲/模擬中週期性事件同步時間計算。