UVA 10951 Polynomial GCD：多項式最大公因式模素數運算

題目大意

給定兩個模素數 n 的多項式 f(x), g(x)，求它們的最大公因式，並將首項係數規範為 1（即乘以首項係數的模逆）。

核心算法：多項式輾轉相除法

同整數 GCD，但除法在模 n 意義下進行。關鍵步驟：

1. 模逆：用擴展歐幾里得算法求 a⁻¹ mod n。
2. 多項式取模：f mod g。令首項係數比為 k = f.lead * g.lead⁻¹ mod n，用 f - k·x^(deg f - deg g)·g 消去 f 的最高次項，重複直到次數 < g。
3. 遞歸 GCD：gcd(f,g) = gcd(g, f mod g)，直到 g 為零多項式。
4. 規範化：結果乘以首項係數的模逆，使首項為 1。

代碼實現

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

int n;
vector f, g;

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

int inv(int a, int n) {
    int x, y;
    exgcd(a, n, x, y);
    return (x % n + n) % n;
}

vector pmod(vector f, vector g) {
    int fz = f.size(), gz = g.size();
    for (int i = 0; i < fz; i++) {
        int k = fz - i - gz;
        if (k < 0) break;
        int coeff = (long long)f[i] * inv(g[0], n) % n;
        for (int j = 0; j < gz; j++) {
            int pos = i + j;
            f[pos] = ((f[pos] - (long long)coeff * g[j]) % n + n) % n;
        }
    }
    // 去除前導零
    vector res;
    int p = -1;
    for (int i = 0; i < fz; i++) if (f[i]) { p=i; break; }
    if (p >= 0) for (int i = p; i < fz; i++) res.push_back(f[i]);
    return res;
}

vector pgcd(vector f, vector g) {
    if (g.empty()) return f;
    return pgcd(g, pmod(f, g));
}

int main() {
    int cas = 0;
    while (cin >> n, n) {
        f.clear(); g.clear();
        int deg, coef;
        cin >> deg;
        for (int i = 0; i <= deg; i++) { cin >> coef; f.push_back(coef); }
        cin >> deg;
        for (int i = 0; i <= deg; i++) { cin >> coef; g.push_back(coef); }

        vector ans = pgcd(f, g);
        int lead_inv = inv(ans[0], n);
        cout << "Case " << ++cas << ": " << ans.size() - 1;
        for (int c : ans) cout << ' ' << (long long)c * lead_inv % n;
        cout << '\n';
    }
    return 0;
}

關鍵細節

• 多項式存儲：vector 低位在前（常數項索引 0），或高位在前？代碼中 f[0] 為最高次項係數（輸入順序）。注意一致性。
• 模運算統一：所有加減乘除均取模 n，減法加 n 再模確保非負。
• 前導零處理：取模後必須去除高位零，否則次數判斷錯誤。
• 遞歸終止：g 為空（零多項式）返回 f。

複雜度分析

• 多項式取模：O(deg(f)·deg(g))。
• 輾轉相除：O(max(deg)³) 最壞，實際極快（次數快速下降）。
• 空間：O(max(deg))。

總結

多項式 GCD 是整數 GCD 在多項式環上的直接推廣。關鍵在於模素數域上除法可行（非零元可逆），利用模逆實現多項式長除法。代碼簡潔，體現代數結構的統一性。