剰余類環

概要

答えが非常に大きくなるので、ある数で割った余りだけ答える問題に使う知識。

アルゴリズム内容

「$10000$ 以下の整数をすべてかけて、$10007$ で割った余りは？」というような問題が出ることがある。
愚直に計算すると桁数がとんでもないことになってしまうので、工夫が必要となる。
そこで登場するのが剰余類環という知識で、身近なところでは時計に使われている。

時計は、$8$ 時の $5$ 時間後は $13$ 時でもあるが、$1$ 時でもある。
日付が変わった $1$ 時間後は、$1$ 時であるが、$25$ 時という場合もある。
これらは、$12$ 時間の差を無視して「$1$ も $13$ も $25$ も実質同じ数」と考えている。
このような考え方を「$12$ を法とする剰余類」「mod $12$ の剰余類」という。
そして、剰余類の上で足し算、引き算、掛け算を考えることを剰余類環という。

例えば mod $5$ の剰余類環の場合。
$3+3$ の答えは本来 $6$ であるが、$5$ の差を無視して $1$ と考える。
$2-4$ の答えは本来 $-2$ であるが、$5$ の差を無視して $3$ と考える。
$4\times4$ の答えは本来 $16$ であるが、$5$ の差を $3$ つ分無視して $1$ と考える。
このように考えると、$0$ から $4$ までのどの数も、和、差、積がまた $0$ から $4$ までのどれかになる。

長い計算をする場合、途中で $5$ の差を無視してもよい。
例えば $(3\times2-2)\times3\times4$ という計算がある場合。
まず $3\times2=6$ を $1$ とする。
次に $1-2=-1$ を $4$ とする。
さらに $4\times3=12$ を $2$ とする。
最後に $2\times4=8$ を $3$ とする。
この方法で計算しても、愚直に計算した $48$ を $5$ で割った余りである $3$ と一致する。

冒頭の問題も同様に、$1$ から $10000$ まで順番にかける中で、$1$ つ掛けるごとに毎回 % 10007 すればよい。
答えは $6991$ となる。

実際には本当に毎回 % m する必要はなく、桁あふれする前に % m すればよい。
余計に行って困るものでもないので、各計算の後に入れておくのが無難ではある。

注意点

引き算が入る場合、負の数に気を付ける。

C++では、負の数に % m を行うと結果も負になる場合がある。
剰余類環での計算を続ける分には影響ないが、最後の答えは $0$ 以上 $m-1$ 以下にする必要がある。
負なら $m$ を加えてから答えること。

掛け算が入る場合、桁あふれに気を付ける。

mod $10^9$ などの場合、計算結果を毎回余りにしていても、掛け算をした直後は int 型からはみ出す。
法が $46341$ より大きく、余り同士を掛ける可能性があるなら long long 型を使うこと。

割り算はそのままではできない。

例えば mod $10$ で $(8+6)/2$ を計算する。
本来の答えは $7$ である。
しかし、$8+6$ の時点で $4$ としてから $2$ で割ると、答えが $2$ になってしまう。
このように、割り算では途中で余りを取ると正しくない答えになることがある。

ただし、法とする数 $p$ が素数であり、割りたい数 $b$ が $p$ の倍数でない場合は、代替手段がある。
フェルマーの小定理より、$p$ を素因数に持たない任意の整数 $b$ について、$b^{p-1}$ を $p$ で割った余りは $1$。
つまり、$b^{p-2}$ を掛ければ、$b$ で割るのと同じ意味を持つ計算になり、実質的に割り算をしたことになる。
累乗は繰り返し二乗法で高速に計算する。
詳しくは「繰り返し二乗法」の記事参照。

関連知識

繰り返し二乗法

素数を法とする剰余類環で割り算を行う場合などに、大きな累乗を高速に計算する。

約数と倍数

互いに素やトーシェント関数など、剰余類環と関係の深い整数の性質を扱う。