素数modの世界 - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

競プロではよく大きな素数で割ったあまりを求めさせる。これは非常に大きな数を取り扱うとき、その取扱い自体に時間が書かり本質のアルゴリズムが評価されないことと、多倍長がある言語とない言語での有利不利をなくすためである。
しかし、modで取る数字は大体素数であるため、そこでいくつかの便利な性質が生じる。

フェルマーの小定理

ある素数pとそれと互いに素の整数aでは、次の関係式が成り立つ
a^p ≡ a (mod p) すなわち
a^(p-1) ≡ 1 (mod p)

この定理から、pと互いに素にある任意のaを指定数のべき乗をするだけ、剰余演算における単位元1が求められる。このことから

aR ≡ 1 (mod p)
R ≡ a^(p-2) (mod p)

と、aごとに対応するRがあり、それをかければ単位元の1が求まるということを意味してる。これは非常に大事である。

オイラーの定理(数論)

あまり出たのを見たことがないけど、フェルマーの小定理を拡張したオイラーの定理というものも存在する。
あるa, nは互いに素の整数とする。(nは素数でなくてもよい)

a^φ(n) ≡ 1 (mod n)

ただし、φ(n)はオイラー関数で、n以下のnと互いに素の自然数の数
どっかででそうだからのせる。

modでの除法

modの世界では割り算は普通の世界とは違いそのまま割ることはできない。これを定義するには、逆元というものを考える。
逆元とは、ある与えられた元を完全に打ち消す元であり、簡単に言うと、ある作業Aに対する逆の作業で、それをするとAする前に戻るものである。
例として、足し算の逆元は引き算、掛け算の逆元は割り算である。
掛け算の逆元は割り算なので、これを考えてみる。
1/a = a^-1 ≡ a^(p-2) (mod p)
つまり、上のようにp-2乗すれば、割り算したということになるのである！
これは割り切れないものでも関係ないため非常に便利。

ちなみに、実装時このような累乗を高速で計算するためには、繰り返し二乗法を使おう。これは検索すれば一杯ヒットするからここでは書かない。

例　M-SOLUTIONS E(600)

この問題は、d/nが割り切れなくともmodの世界では整数であると前提知識で分かっていれば、/(d^n)すれば実質階乗になり計算がすぐに終わるとわかる。
この問題では、modの逆元が非常に重要な役割をはたしていて、(その考えがなければそもそも上のような開放が思いつかないはず)演習効果が高い良問といえる。
事前に累乗の累積積とその逆元、1~10^6+2までの逆元を計算しておけば、modの世界での数式の割り算にも対応できるので簡単に求まる。