Tenka1 Programmer Contest 2019 E問題：Polynomial Divisors

問題. Polynomial Divisors

$n$ 次の整数係数多項式 $f(x) = a_n x^n + a_{n - 1} x^{n - 1} + \cdots + a_0$ が与えられる．任意の整数 $x$ に対して $f(x)$ が $p$ の倍数となるような素数 $p$ をすべて求めよ．

制約： $0 \le n \le 10^4$ ，　 $|a_i| \le 10^9$ ，　 $a_{n} \neq 0$

解法

自力で解けなかったので解説（youtube）を参考にした．

　
素数 $p$ が任意の整数 $x$ に対して $f(x) \equiv 0 \pmod p$ を満たすかを判定する．フェルマーの小定理より $x^{p - 1} \equiv 1 \pmod p$ を満たすので， $p$ を剰余とした演算のもとでは $f$ は $p - 2$ 次の整数係数多項式
　 $f(x) = a_0 + (a_{p - 1} + a_{2p - 2} + \cdots) x^0 + (a_1 + a_{p} + \cdots ) x^1 + (a_2 + a_{p + 1} \cdots) x^2 + \cdots + (a_{p - 2} + a_{2p - 3} + \cdots) x^{p - 2}$
となる．一般に，複素係数の $n$ 次多項式は $n$ 個の複素根を持つ（代数学の基本定理とその初等的な証明 | 高校数学の美しい物語）．このとこから， $p - 2$ 次の整数係数多項式は高々 $p - 2$ 個以下の整数根しか持つことができない．したがって，任意の整数 $x$ に対して $x$ が $f(x)$ の根（ $f(x)$ が $p$ の倍数）となるための必要十分条件は，各係数が $p$ の倍数となることである．以上から，素数 $p$ に対して $p$ が答えに含まれるかを $O(n)$ 時間で判定することができた．

次に，解の候補となる素数の範囲を調べる．演算を $p$ の剰余のもとで行うとき，多項式 $f$ は $p - 2$ 次の多項式となったので， $n + 2 \le p$ のときは各係数が $p$ の倍数となるかを判定することと等しくなる．また， $a_{n} \neq 0$ が保証されているので調べる素数は $n + 1$ 以下の素数と， $n + 2$ 以上の $|a_{n}|$ の素因数のみで十分である．

計算時間： $O(n^2 + n \, d(| a_{n} |))$ （ $d(x)$ は $x$ の約数の個数； $d(|a_{n}|) \le \log_2(|a_{n}|)$ ）

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct Prime {
    int N;
    vector<bool> is_p;

    Prime(int _N) : N(_N), is_p(N + 1, true) {
        is_p[0] = is_p[1] = false;
        for (long long i = 2; i <= N; ++i) {
            if (is_p[i])
                for (long long j = i * i; j <= N; j += i)
                    is_p[j] = false;
        }
    }
    bool operator[](const int idx) const { return is_p[idx]; }
};

template<class T>
std::vector<std::pair<T, T>> PrimeFactorization(T n) {
    std::vector<std::pair<T, T>> pf;
    T m = n;
    for (T i = 2; i * i <= n; ++i) {
        if (m % i != 0) continue;
        T cnt = 0;
        while (m % i == 0) { ++cnt; m /= i; }
        pf.emplace_back(std::make_pair(i, cnt));
    }
    if (1 < m) pf.emplace_back(std::make_pair(m, 1));

    return pf;
}

inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

bool Check(const ll p, const ll n, const vector<ll> &a) {
    if (a[0] % p != 0) return false;
    for (ll s = 0; s <= min(n, p - 2); ++s) {
        ll sum = 0;
        for (ll x = s; x <= n; x += p - 1) sum += a[x];
        if (sum % p != 0) return false;
    }
    return true;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    ll n;
    cin >> n;

    vector<ll> a(n + 1);
    for (int i = n; 0 <= i; --i) cin >> a[i];

    Prime primes(n);
    set<ll> ans_p;
    for (ll p = 2; p <= n; ++p) {
        if (primes[p] && Check(p, n, a)) ans_p.insert(p);
    }

    auto pf = PrimeFactorization<ll>(abs(a[n]));
    for (auto it : pf) if (Check(it.first, n, a)) ans_p.insert(it.first);

    for (auto p : ans_p) cout << p << '\n';

    return 0;
}

解説を読んだ後でも， $a_0$ を $x^0$ の係数でまとめて WA 連発したので反省．
$|a_n|$ の素因数の代わりに $f(1) = a_0 + a_1 + \ldots + a_n$ の素因数を候補としている人がいた（こちらの方が先に思いつきやすそう）．
自力で解けたら楽しいだろうな．