POJ 1061 青蛙約會：擴展歐幾里得算法解一元一次同餘方程

數學建模

兩青蛙同向跳，起點 x,y，步長 m,n，周長 L。求最小 t 使：
x + m*t ≡ y + n*t (mod L)
⇔ (m-n)t ≡ y-x (mod L)
設 a=m-n, b=L, c=y-x，求解 a t ≡ c (mod b)。

擴展歐幾里得求解步驟

1. 計算 d = gcd(a,b)。若 c % d != 0 無解，輸出 "Impossible"。
2. 求解 a p + b q = d，得特解 p0。
3. 原方程通解：t = p0 * (c/d) mod (b/d)，取最小非負解。

代碼實現

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 d = exgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int main() {
    long long x,y,m,n,L;
    while(cin>>x>>y>>m>>n>>L) {
        long long a=m-n, b=L, c=y-x;
        long long d = gcd(a,b);
        if(c % d) { cout << "Impossible" << endl; continue; }
        long long p,q; exgcd(a,b,p,q);
        long long mod = b/d;
        long long ans = (p * (c/d) % mod + mod) % mod;
        cout << ans << endl;
    }
}

注意事項

• a 可能為負，gcd 取絕對值，exgcd 處理負數正確性
• 答案取模時加 mod 保證非負
• t=0 表示起點重合，符合題意