内容別リスト/数学系/剰余類環 - 競技プログラミング用 知識集積所【5/14更新】

---

雑な説明

答えが非常に大きくなるのでコレで割った余りだけ答えてください、という問題に答えるための知識。

レベル

ABCのC問題以降。

アルゴリズム内容

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

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

例えばmod5の剰余類環の場合。
3+3の答えは、本来は6であるが、5の差を無視してこれを1と考える。
2-4の答えは、本来は-2であるが、5の差を無視してこれを3と考える。
4*4の答えは、本来は16であるが、5の差を3つ分無視してこれを1と考える。
このように考えると、0から4までのどの数も、足し算引き算掛け算の答えがまた0から4までのどれかになる。

そして、長い計算をする場合、途中で5の差を無視してもいい。
例えば(3*2-2)*3*4という計算がある場合。
まず最初に3*2で6となるのを、5の差を無視して1とする。
次に1-2で-1となるのを、5の差を無視して4とする。
そして、4*3で12となるのを、5の差を2回分無視して2とする。
最後に、2*4で8となるのを、5の差を無視して3とする。
この方法で計算しても、愚直に計算した48を5の差を7回分無視して3としたものと一致する。

冒頭の問題「10000以下の整数をすべてかけて、10007で割った余りはいくつ？」も同様に考えられる。
つまり、1から10000まで順番にかける中で、1つ掛けるごとに毎回 %= 10007 すればよい。
答えは6991となる。

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

注意点

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

%= m の計算は、負の数に対してはC++の謎仕様により余りも負の数で返される。
剰余類環での計算を続ける分には影響ないが、最後の答えは正の数にしなくてはならない。
「負の数だったら法とした数を加えてから答える」というコードを書き忘れないこと。

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

mod10^9などの場合、油断してはならない。
計算結果は常に10^9未満になるが、掛け算をした後に余りを求める前のところでint型からはみ出る。
法とする数がある程度大きかったら（厳密には46341以上だったら）、掛け算する予定があるならlong long型を使うこと。

割り算はできない。

例えば、mod10の場合に(8+6)/2を計算してみる。
もちろん、正しい答えは7である。
ところが、8+6の時点で答えを4とすると、2で割った結果、答えが2と出てしまう。
このように、割り算は正しくない答えになることがあるので注意。
ただし、法とした数pが素数であり、かつ割りたい数bがpの倍数でない場合は、割り算に代わる計算方法がある。
フェルマーの小定理（未作成）参照。

関連アルゴリズム

• フェルマーの小定理（未作成）

数学の定理。素数を法とする剰余類換で割り算が必要になった場合にお世話になる。

• トーシェント関数（未作成）

素数以外を法とする剰余類換では割り算できないのかというと、割る数次第ではなんとかなる場合がある。
その場合にお世話になる。