Tenka1 Programmer Contest 2019 E - Polynomial Divisors

問題ページ

解法

解説放送で言ってることを自分流に書いたもの
pを一つ固定してその素数が条件を満たすか判定することを考える。pで割り切れるか考えるので以降ではmod pで考える。任意のxに対してf(x)=0 mod pとなればよい。フェルマーの小定理よりx=x^pである。したがって
f(x)
= a[N]x^N + a[N-1]x^(N-1) + … + a[1]x + a[0]
= (a[p-1]+a[2p-2]+…)x^(p-1) + … + (a[2]+a[p+1]+…)x^2 + (a[1]+a[p]+…)x + a[0]
となる。多項式がどのようなxに対しても0になる⇔係数が全て0 であるから係数が全て0か判定することでpが条件を満たすか判定することができる。係数を足してpの倍数になっているかの判定をO(N)ですればよい。
あとはpの候補全てに対してこの判定を行えばよい。pの候補の数を絞ることで全ての候補に対して判定を行っても間に合うようにする。

• p<=N
  10^4以下の素数は大した個数がないので全ての素数に対して判定を行う
• p>N
  フェルマーの小定理を使って変形したようにx^iの係数が複数のaの和になることがない。よってaNがpの倍数でないと条件を満たすことはない。したがってpの候補となるのはa[n]の素因数のみであり大した個数ではないので全てに対して判定を行えばよい。a[n]<0の場合に注意

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

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

    ll n;
    cin >> n;
    vector<ll> a(n+1);
    REP(i, n+1) cin >> a[n-i];

    auto test = [&](ll p) {
        if(a[0]%p) return false;
        vector<ll> sum(p);
        FOR(i, 1, n+1) sum[i%(p-1)] += a[i];
        bool flag = true;
        REP(i, p) if(sum[i]%p != 0) flag = false;
        return flag;
    };

    vector<ll> ans;

    // P <= N
    vector<bool> prime(n+2, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            if(test(i)) ans.push_back(i);
            for (int j = 2 * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }

    // P > N
    ll t = abs(a[n]);
    vector<ll> div;
    for(ll i=2; i*i<=t; ++i) {
        if(t%i==0) div.push_back(i);
        while(t%i==0) t/=i;
    }
    if(t>1) div.push_back(t);
    for(auto i: div) {
        if(i <= n) continue;
        bool flag = true;
        REP(j, n+1) if(a[j]%i != 0) flag = false;
        if(flag) ans.push_back(i);
    }

    for(auto i: ans) cout << i << endl;

    return 0;
}