yukicoder No.308 素数は通れません
問題文
http://yukicoder.me/problems/840
解法
Nが小さければ幅優先探索でいけるけどNが大きすぎる。W=1,2,3,…と増やしていったとき、到達可能範囲がどうなるのか調べていこう。
(1)W=1
(2)W=2
(3)W=3
(4)W=4
(5)W=5
(6)W=6
(7)W=7
(8)W=8
偶数列目は全部緑。だから偶数列目を使えばどこにでも行ける、と思いきや81には行けない。一般にN mod 8=1かつN-8が素数ならNへ移動不可。
(9)W=9
(10)W=10
(11)W=11
(12)W=12
(13)W=13
(14)W=14
偶数列目は全部緑。でもW=8のときと同様に85には移動できない。一般にN mod 14=1かつN-14が素数ならNへ移動不可。
さあW=15を調べようか、とはならない。調べるのはここまででいい。なぜなら「N mod 8=1」かつ「N mod 14=1」かつ「N-8が素数」かつ「N-14が素数」であるようなNは存在しないからである。
証明 N mod 8=1かつN mod 14=1ならばN mod 56=1なので、N=56k+1と表せる。このときN-8=56k-7であるが、これは7の倍数なので素数に成り得ない。
さて、やるべきことはN-8の素数判定だが、$4 \le N \le 10^{24}$というえげつない制約なので$O(\sqrt{n})$のアレでは歯がたたない。そこでMiller-Rabin素数判定法が現れる。
Miller-Rabin法の簡単な説明
まず$p-1=2^e s$の形にする。底となる適当な整数$a$を持ってきて、列$a^s,a^{2s},a^{4s},\ldots,a^{2^e s}$を作ってみる。 pが素数のとき、この列は必ず \[\cdots \to -1 \to 1 \to 1 \to \cdots \to 1\] のように、ある場所で-1が現れてそれ以降1が続くという形になる。もし、 \[\cdots \to 3 \to 1 \to 1 \to \cdots \to 1\] のように-1以外から1に変化していたらpは合成数である。なぜなら$p$が素数のとき二乗して1になる数は±1以外に存在しないからである。 さらに、 \[\cdots \cdots \to 4\] のように最後が1になっていない場合もpは合成数だとわかる。なぜならフェルマーの小定理よりpが素数ならば$a^{p-1}=1$だからである。
ランダムに何個かaを生成して条件を満たすかチェックすれば、高確率で素数かどうかを判定できる。 試す底の個数をkとしたとき失敗する確率は平均して4^-kらしいので、十分大きいkを使えばほぼ失敗することはない。
Nが64ビット整数に収まらないので、実装するときは多倍長整数の使える言語を使おう。ちなみにJavaのBigIntegerにはisProbablePrimeという確率的素数判定を行うメソッドがあるので、それを使ってもいい。
Nが小さいときは振る舞いが変わるので、N=100ぐらいまで幅優先探索で求めるか、解を埋め込んでおく必要がある。
ひとこと
考察パート面白かった。けど制約がきつすぎる気がする。
