Tenka1 Programming Contest 2019 E

問題概要

• Link
• \(n\)次の多項式が与えられるので、どんな数\(x\)を入れても\(f(x)\)が\(p\)で割り切れるような素数\(p\)を列挙せよ.

解法

• すぐに思いつくのは、\(a_0\)から候補を絞って…とやっていく方法だが、判定も含めて間に合いそうにないし、\(a_0 = 0, \sum a_i = 0\)とかだと困る.
• まず、係数のGCDの素因数は、必ず答えに入ることが分かる.
• その他の候補を考える. 素数\(p\)が条件を満たすとき, $$ f(x) \equiv 0 \ (x = 0, 1, \cdots, p-1) $$ が成立する．ゆえに、 $$ f(x) = Q(x)x(x-1)\cdots (x-(p-1)) = Q(x)(x^p - x) $$ が成立する．ここで右の変形はフェルマーの小定理により\(0, 1, \cdots , p-1\)が\((x^p - x=0)\)の解であることからわかる．
• 結局、\(f(x)\)が\(x^p-x\)で割り切れるpを探せば良いが、pは高々\(f(x)\)の次数で抑えられるので、間に合う.