Atcoder Tenka1 Programmer Contest 2019 E - Polynomial Divisors

题意：
给出一个多项式，问有多少个质数\(p\)使得\(p\;|\;f(x)\)，不管\(x\)取何值

思路：
首先所有系数的\(gcd\)的质因子都是可以的。
再考虑一个结论，如果在\(\bmod p\)意义下，多项式中存在\((x^p - x)\)这个因式，那么这个质数\(p\)也是可以的
显然\(p \leq n\)，那么我们只要枚举每个\(\leq n\)的质数，做模\(p\)意义下的多项式除法，判断余数是否为\(0\)即可。

证明：

• 充分性：考虑\(p\;|\;f(x)\)，即\(f(x) = kp\)，即在\(\bmod p\)意义下，\(f(x) = 0\)，根据欧拉定理，分两种情况讨论
  • \(x < p\)，又因为\(p\)是质数，那么显然有\((x, p) = 1\)，那么\(x^{p - 1} \equiv 1 \pmod p\)，有\(x^{p} - x \equiv 0 \pmod p\)
  • \(x \geq p\)，如果\(gcd(x, p)\)不为\(1\)，那么显然有\(gcd(x, p) = p\)，那么已经满足\(p\;|\;f(x)\)，否则套用欧拉定理
• 必要性：如果\(p\;|\;f(x)\)，那么\(0, 1, \cdots, p - 1\)必然为\(f(x)\)的一个根，那么\(f(x)\)有因式\(x(x - 1)(x - 2)\cdots(x - (p - 1))\)。我们考虑这个因式与\(x^p - x\)是等价的，如果不是等价的，那么作差之后，最高次变为\(p - 1\)，而根的个数却有\(p\)个,显然矛盾

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

#define N 10010
int n, a[N], b[N];
bool isprime(int x) {
    for (int i = 2; 1ll * i * i <= x; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
bool ok(int p) {
    if (a[0] % p) {
        return false;
    }
    for (int i = 0; i <= n; ++i) {
        b[i] = a[i];
    }
    for (int i = n; i >= p - 1; --i) {
        (b[i - (p - 1)] += b[i]) %= p;
        b[i] = 0;
    }
    for (int i = 0; i <= n; ++i) {
        if (b[i] % p) {
            return false;
        }
    }
    return true;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        int G = 0; 
        for (int i = 0; i <= n; ++i) {
            scanf("%d", a + i);
            G = gcd(G, abs(a[i]));
        }
        reverse(a, a + 1 + n); 
        vector <int> res;
        for (int i = 2; 1ll * i * i <= G; ++i) {
            if (G % i == 0) {
                res.push_back(i); 
                while (G % i == 0) {
                    G /= i;
                }
            }
        }
        if (G > 1) {
            res.push_back(G);
        }
        for (int i = 2; i <= n; ++i) {
            if (isprime(i) && ok(i)) {
                res.push_back(i);
            }
        }
        sort(res.begin(), res.end());
        res.erase(unique(res.begin(), res.end()), res.end());
        for (auto it : res) {
            printf("%d\n", it);
        }
    //  puts("------------");
    }
    return 0;
}

Atcoder Tenka1 Programmer Contest 2019 E - Polynomial Divisors

原文：https://www.cnblogs.com/Dup4/p/10750749.html