UVA 10951 Polynomial GCD：多項式歐幾里得算法模板

問題描述

給定兩個模 MOD 的多項式，求它們的最大公共多項式（Monic，即首項係數為 1），輸出其次數及係數。

核心算法：多項式長除法 + 遞歸 GCD

與 HDU 3892 相同，但在有限域 Z_MOD 上運算，且要求輸出 Monic 形式。

完整代碼實現

#include 
#include 
#include 
#include 
using namespace std;

#define ll long long

int MOD;

int mod_pow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (ll)res * a % MOD;
        a = (ll)a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 多項式取模：a = q*b + r，返回 r
vector poly_mod(vector a, vector b) {
    if (b.empty()) return a;
    int deg_diff = (int)a.size() - (int)b.size();
    if (deg_diff < 0) return a;
    
    int inv_lead = mod_pow(b[0], MOD-2);
    vector c(deg_diff + 1);
    
    for (int i = 0; i <= deg_diff; i++) {
        c[i] = (ll)a[i] * inv_lead % MOD;
        for (int j = 0; j < (int)b.size(); j++) {
            a[i+j] = (a[i+j] - (ll)c[i] * b[j]) % MOD;
            if (a[i+j] < 0) a[i+j] += MOD;
        }
    }
    
    // 去除前導零
    int p = 0;
    while (p < (int)a.size() && a[p] == 0) p++;
    if (p == (int)a.size()) return {};
    return vector(a.begin() + p, a.end());
}

vector poly_gcd(vector a, vector b) {
    if (b.empty()) return a;
    vector r = poly_mod(a, b);
    return poly_gcd(b, r);
}

int main() {
    int T, Case = 0;
    while (~scanf("%d", &MOD)) {
        vector p1, p2;
        int n1, n2;
        scanf("%d", &n1);
        p1.resize(n1+1);
        for (int i = 0; i <= n1; i++) {
            scanf("%d", &p1[i]);
            p1[i] = (p1[i] % MOD + MOD) % MOD;
        }
        scanf("%d", &n2);
        p2.resize(n2+1);
        for (int i = 0; i <= n2; i++) {
            scanf("%d", &p2[i]);
            p2[i] = (p2[i] % MOD + MOD) % MOD;
        }
        
        // 去除前導零
        auto trim = [](vector& v) {
            int p = 0;
            while (p < (int)v.size() && v[p] == 0) p++;
            if (p == (int)v.size()) { v.clear(); return; }
            v = vector(v.begin()+p, v.end());
        };
        trim(p1); trim(p2);
        
        vector g = poly_gcd(p1, p2);
        
        // 轉為 Monic：首項係數歸一化為 1
        if (!g.empty()) {
            int inv = mod_pow(g[0], MOD-2);
            for (int& x : g) x = (ll)x * inv % MOD;
        }
        
        printf("Case %d: %d", ++Case, (int)g.size() - 1);
        for (int x : g) printf(" %d", x);
        puts("");
    }
    return 0;
}

與 HDU 3892 的關鍵差異

關鍵實現細節

1. Monic 歸一化

GCD 結果首項係數可能不為 1。乘以首項係數的模逆元，使首項變為 1：

int inv = mod_pow(g[0], MOD-2);
for (int& x : g) x = (ll)x * inv % MOD;

2. 多項式表示

vector 高次在前：[a_n, a_{n-1}, ..., a_0]。

3. 輸入處理

• 多測試用例，以 EOF 結束。
• 每個多項式先給次數 n，再給 n+1 個係數。
• 係數模 MOD 歸一化到 [0, MOD-1]。

4. 零多項式處理

• 若輸入含零多項式，trim 後為空向量。
• poly_gcd(a, {}) 返回 a；poly_gcd({}, {}) 返回 {}。
• 最終 g.empty() 時次數為 -1（但題目保證不全零）。

複雜度

• 多項式除法：O(n·m)。
• GCD 遞歸：O(d³)，d 為最大次數。
• 完全滿足題目限制。

總結

UVA 10951 是多項式 GCD 標準模板題。核心代碼與 HDU 3892 高度一致，唯一區別在於輸出 Monic 形式的 GCD 係數。掌握以下關鍵點即可舉一反三：

1. 有限域四則運算（模逆元實現除法）。
2. 多項式長除法（高次在前，前導零清理）。
3. 遞歸歐幾里得算法。
4. Monic 歸一化輸出。

此模板是競程中處理代數問題的基石，可直接用於編碼理論、密碼學、計算幾何等領域。