割った余りの数と四則演算

気づけばだいぶほったらかしになっていた。今日は競技プログラミングで出てくる「～で割ったあまりの数」についての覚え書き。

AtCoderでよく出てくる以下の文。

～を10^9+7で割った余りを求めてください。

競プロ特有の表現なので初見は「なんのこっちゃ？」と思った。要は答えが通常の数値型では表現できない大きな数になるので、1000000007の剰余を答えろということ。

当然割る前の数を求めるとオーバーフローするので、途中途中で剰余をしながら答えを求めるわけだが。

(a + b) % m → (a % m) + (b % m)

各四則演算について上記のような置き換えが可能であることを確かめる。

証明

任意の二つの数x1,x2を以下のように定義する。

x1 = aM + c  
x2 = bM + d  
※Mは除数、a,b,c,dは任意の整数

なお以下では除数Mでxの剰余を取ることを「x mod M」と記載する。

加算

y = x1 + x2
= (aM + c) + (bM + d)
= (a + b)M + c + d

y mod M = c + d
= (x1 mod M)+(x2 mod M)

よって
(x1+x2) mod M = (x1 mod M)+(x2 mod M)

減算

加算と同じである。ただしプログラムの実装では計算過程で負の値が現れる可能性を考慮し、負値の場合Mを加算する処理を入れる。

乗算

y = x1 * x2
= (aM + c)(bM + d)
= abMM + adM + bcM + cd

y mod M = cd
= (x1 mod M)(x2 mod M)

よって
(x1 * x2) mod M = (x1 mod M)(x2 mod M)

除算

ここまでは感覚的に理解してる人も多いと思う。除算だけ少し毛色が異なる。実はここが本題。

除算は以下のようにこねくり回してもMの倍数と定数項の形にできない。

y = x1 / x2
= (aM + c) / (bM + d)
= aM / (bM + d) + c / (bM + d)

つまるところ

(x1 / x2) mod M = (x1 mod M) / (x2 mod M)

は成り立たない。

ここでフェルマーの小定理というものがある。その詳細や証明はひとまず置いておいて、ようするに以下が成り立つ。

Mが素数でaがMの倍数でないとき

a^(M-1) mod M = 1

ちなみに1000000007は素数である。さらに以下のように変形することで(mod M)における「1/a」即ち「aの逆数」が得られる。

(mod M)において

a * a^(M-2) = 1
a^(M-2) = 1/a

よってMが素数のとき除算の剰余は

y = x1 / x2
= x1 * (1/x2)

y mod M
= (x1 mod M) * ((1/x2) mod M)
= (x1 mod M) * (x2^(M-2) mod M)

よって
(x1/x2) mod M = (x1 mod M) * (x2^(M-2) mod M)

となり、各項の剰余で結果の剰余を求めることができる。

以上。終わり。