4問しかないのに数学ギャグ置くの鬼畜か？
お気持ちを書きます。
とりあえず↓を読んで理解できたらこの記事を読む必要はなさそう：
drken1215.hatenablog.com
まずf(x)の内容の素因数は条件を満たすことが簡単にわかります。
「多項式の内容」という概念は過去にも出題されています↓
atcoder.jp
wikipediaへのリンク
ja.wikipedia.org
ところがサンプル1を見ると出力に2があるので他にも解があることがわかります。
このことから実際にpを決めてみないと判定できなさそうな気持ちになります。
そこで問題を二つのパートに分けます。
- pの候補になりうるものを列挙するパート
- pを実際に一つ持ってきたときにf(x)がpで割りきれるかどうかを判定するパート
一つ目のパートはとっつきにくいので、二つ目から考えます。
- f(x)がpで割り切れる ⇔ f(x) ≡ 0 mod p
と言い換えます。
f(x)を整数係数多項式（Z[x]）から、F_p[x]に自然な準同型写像で飛ばすことができます。
（説明するまでもないかもしれませんが、F_pは要素数がpの有限体のことです）
ここで
- 任意のxについて f(x) ≡ 0 ⇔ a=0,...,p-1について f(a) ≡ 0
が言えます（⇒は自明、逆はf(a)≡f(a+p) mod pから明らか）
以上から、ある素数pを固定したとき、O(p)で判定ができました。
このままだとTLEなのでオーダーを改善します。
有名な事実として、体K上の多項式環K[x]はPIDになることが知られています。
ja.wikipedia.org
したがってF_p[x]は整域なので、F_p[x]上でab = 0なら、aかbのどちらかは0になります。
ここで因数定理を用いると、a=0,...,p-1について（因数定理はF_p[x]でも成り立つことに注意）
- f(a) = 0 ⇔ f(x) = (x-a) Q(x) なるQ(x)が存在
となります。
ここで、g(x) = x-aと置くと、a!=bのとき、f(b)=0かつg(b)!=0であるからQ(b)=0であり、この議論を繰り返し用いることで
- a=0,...,p-1について f(a) ≡ 0 ⇔ f(x) = (x-0)(x-1)...(x-(p-1)) R(x) なるR(x)が存在 （☆）
であることが言えます。
これはつまりf(x)が(x-0)(x-1)...(x-(p-1))で割り切れるということです。
mathtrain.jp
ja.wikipedia.org
h(x) = (x-0)(x-1)...(x-(p-1)) とします。
h(x)が高々定数個の項を持つなら、次数下げの要領で、あるpについてO(n)で判定ができることがわかります。
天才ポイント
フェルマーの小定理を思い返すと、x^p = xで、g(x) = x^p - xはa=0,1,...,p-1についてg(a)=0となります。
またg(x)とh(x)の最高次の項の次数はともにpで、その係数は1です。したがって、g(x)とh(x)は一致します。（g(x)に対して☆におけるR(x)は1以外ありえないので）
以上からある素数pに対してO(n)で判定することができました。
残った「pの候補になりうるものを列挙するパート」について考えます
f(x)の内容がpの倍数であるとき、明らかにf(x)≡ 0 mod pであるので条件を満たします。
f(x)の内容の素因数として考えられるものは高々O(log a)個です
p>nのときは一度も次数下げが行えないため、f(x)の内容がpの倍数でないなら、条件を満たすことがありません。したがって、p<=nであるようなものだけ考えればよく、これは素数の分布からO(n / log n)個であることが知られています。
よって、この問題を全体でO(((n / log n) + log a) n)で解くことができました。
