天下一プログラマーコンテスト2019 : E - Polynomial Divisors

ツメが甘すぎる…。
https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_e

問題

N次の多項式が与えられる。
いかなる整数xに対しても、pで割った余りが0になるような素数pを列挙せよ。

解法

まずpを固定して考える。
フェルマーの小定理よりx^p=x (mod p)となる。(x^(p-1)=1とするとx=0で破たんする)
よって、f(x)を(x^p-x)で割っていこう。そうすると(p-1)次以下の多項式になる。
各次数の係数がpの倍数なら、xの値を問わずf(x)はpで割り切れる。

ではどのpで割るべきか。
まずN以下の素数pはすべて列挙して試しておこう。
Nより大きなpについて、多項式の除算をしても商は0である。
よって、この多項式がpで割れるには、元の多項式の各係数がすべてpで割り切れればよい。
言い換えれば係数のGCDの約数が対象となる。

int N;
int A[10101];
ll B[10101];

bool isprime(ll v) {
	for(ll i=2;i*i<=v;i++) if(v%i==0) return false;
	return (v!=1);
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	j=0;
	int g=0;
	N++;
	FOR(i,N) {
		cin>>A[i];
		g=__gcd(g,abs(A[i]));
	}
	
	reverse(A,A+N);
	
	set<int> cand;
	
	for(i=1;i*i<=g;i++) {
		if(g%i==0) {
			cand.insert(i);
			cand.insert(g/i);
		}
	}
	for(i=2;i<=20005;i++) cand.insert(i);
	
	
	FORR(c,cand) if(isprime(c) && A[0]%c==0) {
		ZERO(B);
		FOR(i,N) B[i%(c-1)]+=A[i];
		FOR(i,N) if(B[i%(c-1)]%c) break;
		if(i==N) cout<<c<<endl;
	}
	
	
	
	
}

まとめ

後者はやったけど前者に普通に気が付かなかった…。