Tenka1 2019 E - Polynomial Divisors (橙色, 800 点)

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

問題へのリンク

問題概要

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

制約

• 
• 

考えたこと

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

任意の整数 に対して
⇔

である。なぜなら、 が成立するので、 についてのみ成り立てば十分なことがわかる。

さて次に

⇔
が で割り切れる

であることを示す。これが成り立つ理由は、 を で割って

• 

と表したときに、 より、 が成り立つ。よって、

---

任意の整数 に対して
⇔

⇔
が で割り切れる

---

となることがわかる。

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

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

• 

が成立する。これを示す。まず Fermat の小定理から、 とおくと となることから、

• は で割り切れる

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

• 

とおける。しかしよく見ると、 も も、次数が で最高次係数が なのだ。ということは ということだ。以上から

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

詰め

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

(問題の条件)
⇔
が で割り切れる

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

のとき

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

そうでないとき

この場合は の次数 が 以上でなければならないことがわかる。そうでないなら にならなきゃダメ。

ということで、 を満たす素数 について調べれば良い。 なのでせいぜい 個くらいで済む。

さて、 が で割れるかどうかは、例えば の場合はこんな風にやった。

• 
• 
• 
• 
• 
• 
• 
• 

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

• 

を満たすような 次以下の多項式 を求めることができる。逆に は 次以下なので をこれ以上 で割ってもあまりは である。ゆえに であるかどうかを判定すればよい。

最終的に計算量は

• 最大公約数を求めて素因数分解：
• エラトステネスの篩：
• 各素数について check： 以下の素数の個数を として

#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;
}