HDU 3892 Common Roots：多項式 GCD 判定共同根

問題描述

給定 k 個多項式（模素數 MOD = 999983），判斷它們是否有共同根。若最大公共多項式次數 ≥ 1 則輸出 YES，否則 NO。

數學原理：多項式歐幾里得算法

對多項式 a(x), b(x)，存在唯一 q(x), r(x) 使 a = q·b + r，deg(r) < deg(b)。
若 α 是 a, b 的共同根，則 a(α)=b(α)=0 ⇒ r(α)=0。
因此 gcd(a,b) 的根集 = a,b 的共同根集。
推廣到多個多項式：gcd(p₁, p₂, ..., pₖ) 次數 ≥ 1 ⇔ 存在共同根。

有限域上的多項式運算

模素數 MOD，係數在 Z_MOD 上運算。除法 = 乘模逆元：a/b = a * b^(MOD-2) mod MOD（費馬小定理）。

核心代碼實現

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

#define ll long long
const int MOD = 999983;

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 = a.size() - 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());
}

// 多項式 GCD
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 k;
    while (~scanf("%d", &k)) {
        vector> polys(k);
        for (int i = 0; i < k; i++) {
            int d; scanf("%d", &d);
            polys[i].resize(d+1);
            for (int j = 0; j <= d; j++) {
                scanf("%d", &polys[i][j]);
                polys[i][j] = (polys[i][j] % MOD + MOD) % MOD;
            }
            // 去除前導零
            int p = 0;
            while (p < (int)polys[i].size() && polys[i][p] == 0) p++;
            if (p == (int)polys[i].size()) polys[i].clear();
            else polys[i] = vector(polys[i].begin()+p, polys[i].end());
        }
        
        // 過濾零多項式
        vector> valid;
        for (auto& p : polys) if (!p.empty()) valid.push_back(p);
        
        if (valid.empty()) { puts("YES"); continue; }  // 全零多項式，任意根皆滿足
        if (valid.size() == 1) { puts(valid[0].size()>1 ? "YES" : "NO"); continue; }
        
        vector g = poly_gcd(valid[0], valid[1]);
        for (int i = 2; i < (int)valid.size(); i++)
            g = poly_gcd(g, valid[i]);
        
        puts(g.size() > 1 ? "YES" : "NO");
    }
    return 0;
}

關鍵技術點

1. 多項式表示

vector 存係數，高次在前：[a_n, a_{n-1}, ..., a_0] 對應 a_n x^n + ... + a_0。

2. 多項式除法 (poly_mod)

• 模擬長除法：用 a 的首項消去 b 的首項。
• 因次差 deg_diff = deg(a) - deg(b)，商次數為 deg_diff。
• 每步：c[i] = a[i] / b[0]（模逆元），a[i..i+deg(b)] -= c[i] * b。
• 最後去除前導零得到餘式。

3. 遞歸 GCD

gcd(a,b) = gcd(b, a mod b)，直到餘式為空（零多項式），返回當前除數。

4. 邊界處理

• 零多項式：係數全 0，視為任意多項式的因子。若所有輸入均為零多項式 → 輸出 YES。
• 常數多項式（次數 0）：無根，GCD 次數 0 → NO。
• 前導零：讀入後及 GCD 過程中必須去除。