POJ 1061 青蛙的約會：擴展歐幾里得解同餘方程

題目大意

兩隻青蛙在長度為 L 的圓環上，初始位置 x, y，每次跳躍距離分別為 m, n（單位時間跳一次）。求最少跳躍次數使兩蛙相遇，即求最小非負整數 k 滿足：x + k*m ≡ y + k*n (mod L)。整理得 (n-m)*k ≡ x-y (mod L)，若無解輸出 Impossible。

解法：擴展歐幾里得求線性同餘方程

方程 a*k ≡ c (mod L)，其中 a = n-m, c = x-y。設 d = gcd(a, L)。若 c % d != 0 則無解。否則用擴展歐幾里得求出 a*x0 + L*y0 = d，則 k0 = x0 * (c/d) (mod L/d) 為最小非負解。

關鍵代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

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

int main() {
    LL x, y, m, n, L;
    while (cin >> x >> y >> m >> n >> L) {
        LL a = n - m, b = L, c = x - y;
        LL x0, y0;
        LL d = exgcd(a, b, x0, y0);
        if (c % d) { puts("Impossible"); continue; }
        LL mod = b / d;
        x0 = (x0 * (c / d) % mod + mod) % mod;
        cout << x0 << endl;
    }
    return 0;
}

注意點

• a 可能為負，exgcd 需處理負數（取模時加 mod 再取模）。
• 若 x0 == 0 表示初始即相遇，但題目保證 x != y，故 x0 > 0。