けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Tenka1 2019 E - Polynomial Divisors (800 点)

最大公約数を求めるときに abs つけてれば通ってた。。。
なにこれ悔しすぎる。。。

問題へのリンク

問題概要

 N 次の整数係数多項式  f(x) が与えられる。任意の整数  x に対して  f(x) p で割り切れるような素数  p をすべて求めよ。

制約

  •  0 \le N \le 10^{4}
  •  -10^{9} \le a_{i} \le 19^{9}

考えたこと

めっちゃ好き!!!!!!!!
まず求める条件は

任意の整数  x に対して  f(x) ≡ 0 \pmod p

 f(0) ≡ 0, f(1) ≡ 0, \dots, f(p-1) ≡ 0 \pmod p

である。なぜなら、 f(x+p) ≡ f(x) が成立するので、 x = 0, 1, \dots, p-1 についてのみ成り立てば十分なことがわかる。

さて次に

 f(a) ≡ 0 \pmod p

 f(x) x-a で割り切れる  \pmod p

であることを示す。これが成り立つ理由は、 f(x) x-a で割って

  •  f(x) = (x-a)g(x) + r

と表したときに、 f(a) ≡ 0 \pmod p より、 r ≡ 0 \pmod p が成り立つ。よって、


任意の整数  x に対して  f(x) ≡ 0 \pmod p

 f(0) ≡ 0, f(1) ≡ 0, \dots, f(p-1) ≡ 0 \pmod p

 f(x)  x(x-1)...(x-(p-1)) で割り切れる  \pmod p


となることがわかる。

x(x-1)...(x-(p-1)) ≡ xp - x

次にこれが知らないと非自明なのだが、実は  \mod p

  •  x(x-1)\dots(x-(p-1)) ≡ x^{p} - x

が成立する。これを示す。まず Fermat の小定理から、 g(x) = x^{p} - x とおくと  g(0) ≡ 0, g(1) ≡ 0, \dots, g(p-1) ≡ 0 \pmod p となることから、

  •  x^{p} - x x(x-1)...(x-(p-1)) で割り切れる  \pmod p

ということがわかる。したがってある多項式  a(x) が存在して

  •  x^{p} - x ≡ x(x-1)...(x-(p-1)) a(x) \pmod p

とおける。しかしよく見ると、 x^{p} - x x(x-1)\dots(x-(p-1)) も、次数が  p で最高次係数が  1 なのだ。ということは  a(x) ≡ 1 ということだ。以上から

 x(x-1)\dots(x-(p-1)) ≡ x^{p} - x

が成立することがわかった。

詰め

ここまでの議論で言えたことは、

(問題の条件)

 f(x) x^{p} - x で割り切れる  \pmod p

ということだ。場合分けする。

 f(x) ≡ 0 \pmod p のとき

これは  f(x) の係数がすべて  p の倍数であることを意味する。よって、 f(x) の各係数の最大公約数を求めて、それを素因数分解して出てくる素数たちが答えということになる。

そうでないとき

この場合は  f(x) の次数  N p 以上でなければならないことがわかる。そうでないなら  f(x) ≡ 0 にならなきゃダメ。

ということで、 p \le N を満たす素数  p について調べれば良い。 N \le 10^{4} なのでせいぜい  1000 個くらいで済む。

さて、 f(x) x^{p} - x で割れるかどうかは、例えば  p = 5 の場合はこんな風にやった。

  •  x^{5} ≡ x
  •  x^{6} ≡ x^{2}
  •  x^{7} ≡ x^{3}
  •  x^{8} ≡ x^{4}
  •  x^{9} ≡ x
  •  x^{10} ≡ x^{2}
  •  x^{11} ≡ x^{3}
  •  x^{12} ≡ x^{4}

こんな風に  p-1 ごとに指数が入れ替わる。こうして、

  •  f(x) ≡ h(x) \pmod p

を満たすような  p-1 次以下の多項式  h(x) を求めることができる。逆に  h(x) p-1 次以下なので  h(x) をこれ以上  x^{p} - x で割ってもあまりは  h(x) である。ゆえに  h(x) ≡ 0 \pmod p であるかどうかを判定すればよい。

最終的に計算量は

  • 最大公約数を求めて素因数分解 O(N + \log{a} + \sqrt{a})
  • エラトステネスの篩: O(N\log\log{N})
  • 素数について check:  N 以下の素数の個数を  P として  O(PK)
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

long long GCD(long long a, long long b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (b == 0) return a;
    else return GCD(b, a % b);
}


vector<bool> isprime;
vector<int> Era(int n) {
    isprime.resize(n, true);
    vector<int> res;
    isprime[0] = false; isprime[1] = false;
    for (int i = 2; i < n; ++i) isprime[i] = true;
    for (int i = 2; i < n; ++i) {
        if (isprime[i]) {
            res.push_back(i);
            for (int j = i*2; j < n; j += i) isprime[j] = false;
        }
    }
    return res;
}

int main() {
    long long N; cin >> N;
    vector<long long> a(N+1);
    for (int i = 0; i < N+1; ++i) cin >> a[i];
    reverse(a.begin(), a.end());

    set<long long> res;
     
    // f(x) ≡ 0 の場合
    long long g = 0;
    for (int i = 0; i < N+1; ++i) g = GCD(g, a[i]);
    auto pf = prime_factorize(g);
    for (auto p : pf) res.insert(p.first);

    // N 以下の素数 p をすべて試す
    auto prs = Era(10101);
    for (auto p : prs) {
        vector<long long> c(p, 0);
        for (int d = 0; d < p; ++d) c[d] = a[d] % p;
        for (int d = p; d <= N; ++d) {
            int r = d % (p-1);
            if (r == 0) r = p-1;
            c[r] = (c[r] + a[d] % p) % p;
        }

        bool ok = true;
        for (int d = 0; d < p; ++d) if (c[d] != 0) ok = false;
        if (ok) res.insert(p);
    }
    for (auto p : res) cout << p << endl;
}