AtCoder ABC042 D 初等整数論素数1000000007と合同と逆元

　AtCoder の解説をみたときに 1(mod Y) とかいうよくわからない記法があってスルーしていたが、あれが何なのかやっとわかった。初等整数論の初歩で使う記号だった。D - いろはちゃんとマス目 / Iroha and a Grid は組み合わせを使って解くのだが、都度nCrの階乗を計算させたりするとTLEになってできない。解説をみると逆元とかいうのとともにその(mod m)みたいなのがでてくる。これで計算が非常に圧縮できるらしいのだが、よく知らずに次に進むのも癪なのでググりまくった。初等整数論は初等とつくだけあって簡単なもので高校生でもなんとかわかりそうなものだが高校数学の範囲内ではそんなに詳しくやらないので、自分のように素数とか最大公約数とかは数字のパズル程度のものかと思って以後数学に触れてない人間も多いだろう。もっともコンピュータの基本だったり暗号の基本でもあるのだが、暗号のことがよくわかってなかったのは結局このへんがよくわかってなかったからかもしれない。

　ネット上にある説明はもうわかってる人が基本の説明をおざなりにして書いてるのが多く、そもそもの基本がよくわかってない自分にとってはあんまり意味のないのが多い中で、ここはその歴史から丁寧に説明がしてあってわかりやすかった。

プログラミングの背景：数論

プログラムの背景 (旧ホームページ)

　詳しい説明は上でも見てもらって、ここからは自分がわかった範囲のことを忘れたときのために適当にまとめておく。

　剰余というのは自分程度の人間でも知ってるもので、割った余りのことだが、それをガウス(19世紀初)が合同式というものをひねりだして扱いやすくしたのがこの分野の発展の基礎らしい。

 142536796 - 4 = 6n

　これを ≡ を合同記号として、

142536796 ≡ 4 (mod 6)

　のように表現するのだが、そうすると 142536796 は 6 で割った世界では4ということになる。4 ( mod 6 ) は 6 を法として 4 と読むらしいが、それのわかりやすい応用が曜日ということになる。すべての日が月火水木金土日のどれかで表現できる。集合でいうところの写像か。剰余の世界におさめるということはつまり情報の圧縮になるので、対数などとおなじように巨大な数字を扱いやすくする技術の一つというわけだ。

　ガウスのひねりだした合同式が重要なのはこの ≡ が = と似た性質をもっているから応用しやすいということだ。つまり両辺に演算しても変わらないのでその剰余世界であるかぎり、どこでも応用できる。ということだが問題はうかつに割り算できないことで、割り算に相当するものとして逆元が使われることになった。逆元はかけると剰余が1になる数のことで一意に決まり、拡張ユークリッド互除法などで導ける。ABC042 D の解法ではフェルマーの小定理の両辺に逆元をかけて導いている。素数1000000007などを使うのは 2³¹が2147483648だからちょっと前のコンピュータだと都合がいいというところか。x の逆元を x^-1とも表記し、現実にフェルマーの小定理 X^p-1= 1 (mod p) の両辺に x ^-1をかけるという操作をして逆元を出すという演算もできている。というか逆行列っぽいな。