pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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ぐらいまで幅優先探索で求めるか、解を埋め込んでおく必要がある。

yukicoder No.308 素数は通れません

yukicoder No.308 素数は通れません

ひとこと

考察パート面白かった。けど制約がきつすぎる気がする。