Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

天下一2019 - E Polynomial Divisors ~因数定理と合同~

atcoder.jp

因数定理の合同による式変形を知っていれば命題の同値条件でサクサク行く問題であった。その先にも少してこずるものもあり、800点としては妥当だと思う。(水色の雑魚が言ってる)

この問題、はじめにxは任意の整数という条件になってる。ここで、受験数学の整数論を思い出せ。
余りで考えろ!
余りで考えることによって、素晴らしいことに無限のものは有限個のものになるのである!
なぜ忘れたんでしょうね。。。これだから数学4○点取るんですね・・・

この問題にこれを適用させる。

素数pでのあまりを考えると、すべて整数になるというのは f(0) ≡ f(1) ≡ f(2) ≡ ... ≡ f(p - 1) (mod p) (式1)を満たすことである。

大量にf(a) = 0が並ぶとき、受験数学でも使ってるアレが使えますよね?
因数定理くんですね。使いましょう。

f(x)≡x(x - 1)(x - 2)...(x - (p - 1))A(x) (mod p)
ただし、A(x)は適当な多項式とする。

さあ、ここまで来ました。受験数学でもここまで来れますね。
ここで、知識ゲー的な定理による変換をする。

x(x - 1)(x - 2)...(x - (p - 1)) ≡ x^p - x ≡ 0 (mod p) (式2)

はい。何言ってるかよくわかんないから証明する。

pは素数なので、フェルマーの小定理によって、(pは素数じゃなく、xと互いに素であればいいけど、この時xはいろんな値をとりうるから結局pは素数)
x^p≡x(mod p)
が成り立つ。つまり、(式2)の右辺はxにかかわらず、常に0が成り立つ。
一方(式2)の左辺はmod pで何を代入しても0になる。
ここで、両側の次数を見ると、同じp次式であることがわかる。
同じ次数で、どんなxでも同じように0と合同なので、上記の定理は示せた。

さて、この定理を使って考えてみると、最初に定義した(式1)と同値な式、
f(x) ≡ (x^p - x)B(x) ≡ 0(mod p) (式3)
を導ける。ただし、A(x)と同様にB(x)を定める。

ここまできました。この問題のキモも大体終わりました。しかしまだ考察は続く。

さて、f(x)がx^p - xでmod pで割り切れるためにはどのようなpにすればいいのでしょうか?
この時、f(x) ≡ 0をまず満たせるものを考える。これは、各係数の絶対値の最大公約数をとることで、その数の素因数である。ここまではそれなりに自明なやつ。

じゃこれだけかって言ったらんなわけないですね。作問者がだてに800にこんなことを置くわけないじゃないですか。

ここで、非自明なpを見つけよう。
まず、非自明なものとは何かを定義する。それはすなわち
f(x)の係数の最大公約数的に絞れない、どれがどれかわからない素数
ここで、0と合同になるもう一つの条件を(式3)から読み取ろう。
そう、x^p - xに割り切れることである!
このことからpは上に有界とわかる。pは最大Nまでしか行けない。
つまり、どうやって割るかという話になるね。
しかし、ここでテクニック。面倒な正式の割り算なんてしなくていい。(by けんちょんさんのブログ)

(式2)のとおりに、フェルマーの小定理を利用すると、p次以上の項はmod pの条件下でp - 1次以下にまとめることができる(x^(p+1) -> x^2)。また、mod p で考えるので、各項の係数もmod pしても問題はない。(どうせ最終的に0と合同すればいい)
こうやって最大p - 1次の式を作ることができる。
この式はmod pでもともとのf(x)と同じように0と合同である。
ちなみに、この変換自体がp次の式で割ってるようなもん(つまりx^p - x。合同式ではB(x)をかけて合同だったので、x^p - xで割っても正しい)である。変換で出てきた最大p - 1次の式はあまり。

あとは、あまりの式の各項がすべて0になっていれば、あまりなどなかったんや!と非自明な素数として見つかる。ぬでたレぬでたレ。

日ハム勝てるといいね。

まとめ
・ 整数問題ですべての○○に対して成り立つ=あまりをとれ
・ x (x-1) ... (x - (p - 1)) ≡ x^p - x (mod p)
・ 整式の割り算のスマートなやり方として、f(x)をフェルマーの小定理を利用した次数下げを行って、f(x)=g(x)*A(x)の割る式g(x)よりも次数を下げれば、それは余りとなるということを利用する!