競技プログラミングにおける剰余の基礎と mod 逆元

Pocket

▲「お兄ちゃん、最近『ABC 緑 diff を攻略する』っていうスライドを見たんだけど、要求される数学の知識に $\bmod$ 関連の知識が載ってるんだよね」

■「ああ、最近は $\bmod$ 逆元を使う問題も緑あたりの難易度になるんだね」

▲「で、このスライド、必要って言っときながら説明しないんだよねー」

■「そうなんだ。実装は言語によるから、各自で調べてってことなのかな」

▲「だから、教えて？」

■「それはいいんだけど、そもそもどこまで知ってるの？」

1 mod の定義
2 mod 上での和・差・積
3 mod 上で割り算は難しい！
4 mod 上での逆数？
5 mod 逆元の計算方法
6 累乗の高速化：繰り返し二乗法

mod の定義

▲「$\bmod$ っていうのは、割った余りの話だよね」

■「うん。整数を正整数で割ったときの余りを考える話だね」

▲「で、“$a$ と $b$ をそれぞれ $M$ で割った余りが一致する” っていうのを、こんなふうに書くんだよね。“合同式” っていう名前があって、『$a$ と $b$ は $M$ を法として合同』って言ったりする」

$$a\equiv b \pmod{M}$$

例えば、$7$ と $22$ は $5$ で割った余りが等しいので、

$$7\equiv 22\pmod{5}$$

また、$7$ と $13$ は $5$ で割った余りが等しくないので、

$$7\not \equiv 13\pmod{5}$$

■「そうだね。$\bmod$ について、別の定義は知ってる？」

▲「別の定義？ “割った余り同じ” 以外にあるの？」

■「うん。こっちのほうが使いやすいから、知っておくと良いよ」

$\bmod$ の定義その②

$a\equiv b\pmod{M}\Leftrightarrow a-b=kM$ を満たす整数 $k$ が存在する

▲「差が $M$ の倍数ってこと？　確かに、割った余りが同じだとそうなるね」

$a=q_aM+r, b=q_bM+r$ のとき、$a-b=(q_a-q_b)M$

■「逆も正しいよ。つまり、この定義は “割った余りが同じ” とちゃんと同値になっている。だから、こっちを $\bmod$ の定義とすることができる」

逆：

$a-b=kM$ のとき、$a=qM+r$ とすると、$b=a-kM=(q-k)M+r$ より、$b$ を $M$ で割った余りも $a$ と同じく $r$ になる

▲「へー、なんでこっちの方が使いやすいの？」

■「”割った余り” という表現が無いからかな。割り算は厄介だから、割り算を使わずに定義できるのが嬉しいんじゃないかと思うよ」

mod 上での和・差・積

▲「あと、足し算と引き算と掛け算は雑にやっても大丈夫！」

■「そうなんだけど、もうちょっと正確に記述したいなあ」

▲「えっと、$a$ を $M$ で割った余りって、数学的にはどう書くの？」

■「うーん、どうだろう。競プロの解説だと $a \bmod b$ という書き方を見るね。$24\bmod 10=4$ みたいな」

▲「$\bmod$ ってそんな使い方もできるんだ。じゃあ、こんなイメージかな」

$$(a+b)\bmod M\equiv (a\bmod M)+(b\bmod M)$$

$$(a-b)\bmod M\equiv (a\bmod M)-(b\bmod M)$$

$$(a\times b)\bmod M\equiv (a\bmod M)\times (b\bmod M)$$

■「うん。それはすべて成り立つね。証明するときは、こうやるのが一般的かな？」

$$a\equiv b \pmod{M}$$

$$c\equiv d \pmod{M}$$

ならば、

$$a+c\equiv b+d \pmod{M}$$

$$a-c\equiv b-d \pmod{M}$$

$$ac\equiv bd \pmod{M}$$

証明：

仮定より $a-b=jM,c-d=kM$ を満たす整数 $j, k$ が存在して、

$(a+c)-(b+d)=(a-b)+(c-d)=(j+k)M$

$(a-c)-(b-d)=(a-b)-(c-d)=(j-k)M$

$ac-bd=ac-(a-jM)(c-kM)=(ak+cj-jkM)M$

▲「おー、さっきの定義を使うと証明が簡単だね」

■「積で成り立つから、累乗でも成り立つ」

非負整数 $n$ について、$a\equiv b\pmod{M}\Rightarrow a^n\equiv b^n \pmod{M}$

▲「これで、和・差・積・累乗と $\bmod$ は自由に入れ替えても良いってことになるんだよね？」

■「そうだね。最後に $\bmod$ を取るのと、各演算ごとに $\bmod$ を取るのとで結果が一致する。ただし、負の数の $\bmod$ を取るのはプログラミング言語やコンパイラによっては変なことになるから、$M$ を足すとかして正の数にしてから扱うようにね」

mod 上で割り算は難しい！

▲「でも、割り算はできないんだよね？」

■「素直にはできないね。つまり、以下の式は常に成り立つとは限らない」

これは偽！

$$na\equiv nb \pmod{M}\Rightarrow a\equiv b\pmod{M}$$

▲「これってなんでなの？」

■「さっきの定義を使って書いてみるとどうなる？」

▲「えっと、左側はこうなるよね」

$$na-nb=jM$$

■「うん。右側は？」

▲「こうだね」

$$a-b=kM$$

■「左から右を言おうとしてみると、どうなる？」

▲「$na-nb=n(a-b)=jM$ だから $a-b=kM$ 、って言いたいんだよね。それは、$n(a-b)$ が $M$ の倍数だから $a-b$ が $M$ の倍数だ！っていうことなんだけど、たしかに、$n$ と $M$ が互いに素と限らないからダメだね」

■「そうだね。実際、$9\equiv 3 \pmod{6}$ だけど、両辺を $3$ で割ったら $3\not \equiv 1\pmod{6}$ となるね」

▲「これは、$9-3=3(3-1)=1\times 6$ だけど、$6$ の約数が $3$と $(3-1)$ に分かれて入ってるから $(3-1)$ が $6$ の倍数になってないってことだね」

■「そう。でも、$n$ と $M$ が互いに素だったら割り算ができる」

▲「割り算ができるっていうのは、例えば $5$ と $6$ が互いに素だから $35\equiv 5\pmod{6}$ の両辺を $5$ で割って $7\equiv 1\pmod{6}$ にする、みたいな操作が許されるってこと？」

■「うん。つまり、こういうこと。証明はさっきの議論と、 $n$ と $M$ が互いに素であることを使えばいい」

$$na\equiv nb \pmod{M}$$

で、$n$ と $M$ が互いに素ならば、

$$a\equiv b\pmod{M}$$

▲「うーん、でもこれって使いにくくない？」

■「どういうこと？」

▲「競プロでやりたいのは、$na\bmod M$ の値が分かっているときに、$a\bmod M$ の値を調べるってことだよね。$na$ そのものの値が分からないから、両辺を $n$ で割ってーみたいなのは使えないんじゃないの？」

■「ああ、そうだね。じゃあ、$na\bmod M$ の値から $a\bmod M$ を計算する方法を教えようか」

▲「最初からその話で良かったんじゃない？」

■「いやいや、基礎を理解しておくのは大事だよ」

mod 上での逆数？

■「さて、$\bmod$ の世界では、和・差・積・累乗は自由にできる」

▲「さっき確認したね」

■「この状態で、割り算について考えたい。どうしようか」

▲「あたしに聞かれても」

■「割り算はしたくないけど、掛け算ならできるんだ」

▲「うん」

■「つまり、割り算を掛け算に変換することができれば、割り算ができるようになる」

▲「$\bmod$ じゃない普通の世界だと、割り算は逆数を掛けるのと同じだよね、ってこと？」

■「そうそう。では、逆数とは何でしょう？」

▲「$n$ に掛けて $1$ になる数が、$n$ の逆数だよね」

■「正解。じゃあ、$\bmod$ の世界でも逆数を考えてみよう」

▲「$n$ に掛けて $M$ で割った余りが $1$ になる数を考えるってこと？」

■「そう。そんな数が存在するかどうかは分からないけど、仮に存在したとして、それを $u$ としよう」

▲「$n$ の逆だから $u$ って……　つまり、こういうことだよね」

$$nu\equiv 1 \pmod{M}$$

■「うん。そういう $u$ のことを、よく $n$ の $\bmod M$ での逆元という。”逆元” という言葉はもっと広い意味の言葉だけど、競プロの文脈では $\bmod$ 上での積の逆元のことを表すことが多いね」

▲「逆元、聞いたことあるよ。でも、本当にこれを掛けることが割り算になるの？」

■「じゃあ確かめてみよう。$na$ を $M$ で割った余りが $r$ であるとしよう。このときに、$a$ を $M$ で割った余りが知りたいから “$r$ を $n$ で割る” という操作をしたい。どうすればできると思う？」

▲「話の流れ的に、$r$ に $u$ を掛けることが、$r$ を $n$ で割ることに対応しそうだよね」

■「やってみて」

▲「$ru$ を $M$ で割った余りを計算すれば良いんだよね。まず前提条件から始めるのがいいから、この式が使えて……」

$$na\equiv r \pmod{M}$$

■「うんうん」

▲「$ru$ のことが知りたくて、掛け算は自由にできるから両辺に $u$ を掛けて……」

$nau\equiv ru \pmod{M}$

■「いい感じだね」

▲「この左辺が $nu\times a$ になるから……なるよね？」

■「うん。整数で掛け算の順序交換ができるから、大丈夫」

▲「じゃあ、こうか！」

$$ru\equiv nu\times a\equiv 1\times a\equiv a\pmod{M}$$

■「正解！」

▲「これは、$r (=na\bmod M)$ だけを知ってる状態から、$n$ の逆元である $u$ を使って、$a\bmod M$ を計算できたってことだね」

■「そうだね。ちなみに、$n$ の逆元のことを $n^{-1}$ と書くことがある。ただしこれは $\frac{1}{n}$ とは別物だから要注意」

▲「エヌのマイナスいちじょう？」

■「エヌインバースと読むのが良いかな。逆関数 $f^{-1}(x)$、逆行列 $A^{-1}$ みたいに、”逆” という概念には “inverse” という言葉を使うことが多いね。とにかく、これで $\bmod$ 上で割り算ができたことになる」

▲「やったー！」

mod 逆元の計算方法

▲「いや、やったー！じゃないよ」

■「まだ言ってないことがあったね」

▲「そうだよ！　そもそも、$nu\equiv 1$ になるような $u$ ってどうやって見つけるの？　ていうか存在するの？」

■「そこで今回ご紹介するのがこちら！　フェルマーの小定理でございます！」

▲「いきなり通販番組始まったよ」

■「フェルマーの小定理というのは、こんな定理」

フェルマーの小定理：

$P$ が素数のとき、$P$ の倍数でない整数 $a$ について、以下が成り立つ

$$a^{P-1}\equiv 1\pmod{M}$$

▲「フェルマーの小定理、聞いたことはあるんだけど、こういう内容なんだね」

■「そう。法が素数のときは、これを使って逆元が簡単に計算できる」

▲「例えば、$P=7, a=2$ とすると、$2^{7-1}=64\equiv 1 \pmod{7}$ っていうことだよね」

■「そうそう。証明はちょっとややこしいから、Wikipedia を見るなり検索するなりで調べてほしい。証明の概要はこんな感じ」

フェルマーの小定理の証明の概要：

数学的帰納法を用いて、補題「素数 $P$ と整数 $a$ について $a^P\equiv a\pmod{P}$」が成り立つことを示す。ここで $a$ は $P$ と互いに素と限らない。

まず、二項定理を用いて $(m+1)^P\bmod P$ が $(m^P+1)\bmod P$ と一致することを示す。

次に、これを用いて「$a^P\equiv a$ が成り立つならば $(a+1)^P\equiv a+1$ が成り立つ」ということを示す。

そして、$a=1$ で $a^P\equiv a$ が成り立つことから数学的帰納法によって任意の正整数で補題が成り立つことを言う。

そうすると、$a$ と $P$ が互いに素である場合に、両辺を $a$ で割ることができるため、定理が示される。

$a$ が $0$ のときは $P$ の倍数であるため定理の真偽とは無関係。$a$ が負のときは、$P$ が $2$ または奇数であることを利用する。

▲「で、これをどう使うの？」

■「$n$ に掛けて $1$ になる数が、$n$ の逆元だったわけだ。そして、フェルマーの小定理によると、これが成り立つ」

$$n^{P-1}\equiv 1 \pmod{P}$$

▲「あ、てことは、$n^{P-2}$ が $n$ の逆元ってことだ！」

$$n\times n^{P-2}\equiv 1\pmod{P}$$

■「その通り。例えば、$P=7, a=2$ のときは、$2^5=32\equiv 4$ が $2$ の逆元。実際、$2\times 4=8\equiv 1$ だ。ちなみに $P$ は素数だから $2$ 以上で、指数が負になる心配は無い」

$\bmod$ 逆元の使い方の例：

$2x\equiv 5\pmod{7}$ のときに $x \bmod 7$ を知りたい！

でも $2x$ の値は分からない！

（実は $x=55$ なので $x\bmod 7=6$）

$\bmod 7$ での $2$ の逆元は $4$ だから、$5$ に $4$ を掛ければ良いんだ！

ということは、$x\bmod 7=(5\times 4)\bmod 7=20\bmod 7=6$ だ！（正解）

▲「法が素数じゃない場合も、$n$ と法 $M$ が互いに素だったら割り算ができるって話だったけど、逆元は無いの？」

■「あるよ。競プロではあまり使わないけどね。法が素数じゃない場合は、オイラーの定理というものが使える」

オイラーの定理：

整数 $n$ と正整数 $M$ が互いに素のとき、以下が成り立つ。

$$n^{\phi(M)}\equiv 1\pmod{M}$$

ただし、$\phi(M)$ は $M$ 未満で $M$ と互いに素な整数の個数を表す “オイラーの $\phi$ 関数”

▲「$\phi$ 関数？」

■「例えば、$\phi(10)$ は $1, 2, 3, 4, 5, 6, 7, 8, 9$ のうち $10$ と互いに素なものの個数だから、$1, 3, 7, 9$ の $4$ 個。つまり、$\phi(10)=4$ となる」

▲「じゃあ、$\bmod 10$ での $3$ の逆元は指数を 1 引いて $3^{\phi(10)-1}=3^3=27\equiv 7$ ってことだね。たしかに、$3\times 7=21\equiv 1$ になってるね」

■「これで逆元を計算できるから、$\bmod$ での割り算ができるようになったね」

累乗の高速化：繰り返し二乗法

▲「いやいやいや」

■「まだ何か問題が？」

▲「競プロだと、$P=10^9+7$ とかが多いけど、$n^{P-2}$ を計算するのは時間的に無理だよね」

■「ああ、そうだね。繰り返し二乗法の説明もしようか」

▲「繰り返し二乗法？」

■「$n^k$ を $O(\log k)$ で計算する方法。$\bmod$ にも対応できる」

▲「あー、なんかよく分かんないままコピペして使ったことあるかも」

■「ちゃんと理解して使おうね」

▲「はーい」

■「コンセプトとしては、$n^1, n^2, n^4, n^8, \dots$ を事前に計算しておいて、これらを組み合わせて $n^k$ を計算するという感じ。事前計算する値は、$n^8=(n^4)^2$ という形で $O(1)$ で作っていける」

▲「あー、$k$ の二進数表記を使うってこと？」

■「察しが良いね。例えば $k=19$ のとき、$1+2+16$、つまり、二進数で表すと $10011_{(2)}$ になるよね」

▲「数の右下の $(2)$ っていうのは、”二進数表記” っていう意味だよね」

■「そうそう。だからこの場合は、$n^{19}=n^1\times n^2\times n^{16}$ として計算できる。」

▲「なるほどー。指数 $k$ が $10^{18}$ ぐらいまでなら、$n^{2^{60}}$ ぐらいまで、$60$ 個計算しておけば大丈夫？」

■「うん。ただし、実装では $60$ 個用意してから計算するんじゃなくて、$n^{2^m}$ を計算しながら答えに掛けていくのが良いよ。実装例がこれ」

// n の k 乗を mod で割った余りを計算
long long power_mod(long long n, long long k, long long mod) {
    long long result = 1;
    // k を右シフトしつつ n を 2 乗していく
    while (k > 0) {
        // k の最下ビットが 1 なら、今の n を答えに掛ける
        if ((k & 1) == 1) result = (result * n) % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return result;
}

// n の k 乗を mod で割った余りを計算

long long power_mod(long long n, long long k, long long mod) {

long long result = 1;

// k を右シフトしつつ n を 2 乗していく

while (k > 0) {

// k の最下ビットが 1 なら、今の n を答えに掛ける

if ((k & 1) == 1) result = (result * n) % mod;

n = n * n % mod;

k >>= 1;

}

return result;

}

▲「右シフトって、 2 で割るのと同じやつだっけ？」

■「うん。例えば、$3^{19} \bmod 100$ の計算では、こんな流れになる」

$n=3, k=19=10011_{(2)}, result=100$
$k>0$ なので、ループ 1 回目
- $k$ の最下ビットが $1$ なので、$result$ に $n=3$ を掛けて $100$ で割った余りをとって、$result=3\equiv 3^{1_{(2)}}$
- $n$ を 2 乗して $100$ で割った余りをとって $n=9$
- $k$ を右シフトして、$k=9=1001_{(2)}$
$k>0$ なので、ループ 2 回目
- $k$ の最下ビットが $1$ なので、$result$ に $n=9$ を掛けて $100$ で割った余りをとって、$result=27\equiv 3^{11_{(2)}}$
- $n$ を 2 乗して $100$ で割った余りをとって $n=81$
- $k$ を右シフトして、$k=4=100_{(2)}$
$k>0$ なので、ループ 3 回目
- $k$ の最下ビットが $0$ なので、$result$ はそのまま。$result=27\equiv 3^{011_{(2)}}$
- $n$ を 2 乗して $100$ で割った余りをとって $n=61$
- $k$ を右シフトして、$k=2=10_{(2)}$
$k>0$ なので、ループ 4 回目
- $k$ の最下ビットが $0$ なので、$result$ はそのまま。$result=27\equiv 3^{0011_{(2)}}$
- $n$ を 2 乗して $100$ で割った余りをとって $n=21$
- $k$ を右シフトして、$k=1=1_{(2)}$
$k>0$ なので、ループ 4 回目
- $k$ の最下ビットが $1$ なので、$result=27$ に $n=21$ を掛けて $100$ で割った余りをとって、$result=67\equiv 3^{10011_{(2)}}$
- $n$ を 2 乗して $100$ で割った余りをとって $n=41$
- $k$ を右シフトして、$k=0=0_{(2)}$
$k=0$ なので、ループを抜ける
$result=67$ を返す

▲「Google で計算したけど、$3^{19}=1162261467$ らしいから、$100$ で割った余りが $67$ で一致してるね。これ、手計算でも使えるね」

■「そうだね。というか、アルゴリズムはだいたい手計算の役に立つものだよ」

▲「これで $\bmod$ の問題は完璧だね！」

■「まあ、そうかな」

▲「なにその言い方」

■「例えば逆元をたくさん計算する必要があるときに、$O(\log M)$ がちょっと邪魔になることがあるかなあとか」

▲「えー、それぐらい一瞬でしょー。ていうか、そんなに逆元をたくさん計算することってある？」

■「組合せ ${}_n\mathrm{C}_k$ をたくさん計算するときとか」

▲「あれ？　そもそも ${}_n\mathrm{C}_k$ をたくさん計算って今の状態でできる？」

■「それはできるよ。組合せは以下の式で計算できるから、$n$ の最大値までの非負整数の階乗の $\bmod M$ を事前に計算しておけば、逆元を使った割り算で計算できるよ」

$${}_n\mathrm{C}_k=\frac{n!}{k!(n-k)!}$$

より、$M$ が素数のとき

$${}_n\mathrm{C}_k\bmod M\equiv n!\times k!^{M-2}\times (n-k)!^{M-2}$$

▲「じゃあ無敵じゃん」

■「まあ困る場面はあまり無いかもしれないけど、僕は素数 $\bmod$ での $n$ 以下の非負整数の逆元・階乗・階乗の逆元を $O(n)$ で計算するクラスを用意しているから、また今度紹介するよ」

▲「フェルマーさんを使うと $O(n\log M)$ だから、$\log M$ 倍速いってことだね」

■「そうそう。$M$ が $10^9$ ぐらいだったら $30$ 倍」

▲「$30$ 倍って聞くと速そうに聞こえるね」

■「今日は長くなったし、また今度ね」

Pocket