10^9+7で割った余りを考える際の四則演算を解説

はじめに

　本記事は競技プログラミング初心者向けに$10^9+7$で割った余りを考える際の四則演算について解説します。AtCoderでは最終的な回答を$10^9+7$で割った余りを出力する問題（例えばABC156D問題やABC34C問題）が出題されることがありますが、ここで馬鹿正直に問題で指定された通りの計算を行いプログラムの最後で答えを$10^9+7$で割るような処理を書いてもほとんどの場合計算の途中でオーバーフローしてしまい、正しい答えを得ることはできません。プログラムの最後で割り算を行うのではなく、計算の途中で細かく剰余を取りオーバーフローを防ぐ必要があります。足し算、引き算、掛け算に関しては高校数学が得意だった人であれば競技プログラミングのために勉強するまでもなく理解していることが多いと思いますが、割り算に関しては競技プログラミングの問題として出会うまで知る機会がなかったという人がほとんどだと思います。この記事では前半で足し算、引き算、掛け算のやり方を簡単に解説した後、後半ではフェルマーの小定理、二分累乗法を使った割り算のやり方を解説します。

変数の定義

　解説をスムーズに行うため以下のように定数及び変数を定義しておきます。
$M = 10^9+7$
$x = a \times M + b$
$y = c \times M + d$
ただし$x,y,a,b,c,d$は整数で、$x,y$は$0$以上であり、$b,d$は$0$以上$M$未満である。

足し算、引き算、掛け算について

　足し算、引き算、掛け算の場合はとても簡単です。以降の合同式では特に表記がない場合$\pmod M$が省略されています。

\begin{align}
x + y &\equiv (a \times M + b) + (c \times M + d) \\
&\equiv (a + c) \times M + (b + d) \\
&\equiv b + d
\end{align}

上の式から分かるように$(x + y) \% M$は$b,d,M$のみを使って表すことができます（ただし$\%$は割り算の余りを求める二項演算子です）。つまり、二つの整数の和を割った余りを考えたいときは常に余りの部分だけを考えればよいというわけです。引き算、掛け算に関しても同様な性質が成り立ちます。この性質の利用例をソースコードで紹介します。

下のプログラムは$100!$を$M$で割った余りを求めるプログラムです。このプログラムでは計算の途中でオーバーフローしてしまうため正しい結果を得られません。

program1.cpp

#include<iostream>

typedef long long LL; //long longは64bitの整数型
const LL M = 1000000000 + 7;
using namespace std;

int main(void) {
    LL ans = 1;
    for (LL i = 1; i <= 100; i++) {
        ans *= i; //ここの計算でオーバーフローが発生
    }
    ans %= M;
    cout << ans << endl;
}

上のプログラムを改良して細かく剰余を取るように変更します。

program2.cpp

#include<iostream>

typedef long long LL; //long longは64bitの整数型
const LL M = 1000000000 + 7;
using namespace std;

int main(void) {
    LL ans = 1;
    for (LL i = 1; i <= 100; i++) {
        ans *= i;
        ans %= M; //一回掛け算するたびに剰余を取る
    }
    cout << ans << endl;
}

for文の中で細かく剰余を取ることでオーバーフローを防ぎ正しい結果を得られるようになります。

割り算について

　割り算の場合は足し算のように簡単ではありません。$x$が$y$で割り切れるとき$(x \div y) \% M$を$b,d,M$で表せるという点は足し算と同じですが、$x \div y \equiv b \div d$が成立するとは限らないことに注意する必要があります。
　スムーズに説明するため以降の割り算に関する説明においては$x$は$y$で割り切ることができ、$M$と$y$は互いに素であるとします。

フェルマーの小定理

　割り算のやり方を理解するために必要な知識の一つ目はフェルマーの小定理です。フェルマーの小定理の証明や細かな性質はこの記事の本質的な内容ではないため高校数学の美しい物語を参照してほしいのですが、特に重要な内容は下記の事実です。

pが素数で、aがpの倍数でない正の整数のとき \\
a^{p-1} \equiv 1 \pmod p

この定理を使って$(x \div y) \% M$を$b,d,M$の式で表すことができます。

\begin{align}
x \div y &\equiv x \div y \times 1 \\
&\equiv x \div y \times y^{M - 1} \\
&\equiv x \times y^{M - 2} \\
&\equiv (a \times M + b) \times (c \times M + d)^{M - 2} \\
&\equiv b \times d^{M - 2}
\end{align}

この時点で$(x \div y) \% M$を$b,d,M$で表すことはできていますが、この計算を愚直に実行すると$10^9$回程度の掛け算が必要で競技プログラミングにおいては全く使い物になりません。そこで必要になってくる二つ目の知識が二分累乗法です。

二分累乗法

　割り算のやり方を理解するために必要な知識の二つ目は二分累乗法です。これは通常$N-1$回の掛け算が必要な$N$乗の計算を$log_2N$回程度の掛け算で行う方法です。ここでは具体例として$3^{1030}$を二分累乗法で求めてみます。まず$1030$を$2$の累乗数の和の形になるように分解します。つまり

\begin{align}
1030 &= 1024 + 4 + 2 \\
&= 2^{10} + 2^2 + 2^1
\end{align}

という形に変形します。この処理は$1030$を二進数に変換していると言ってもいいです。次に$3^{1024},3^4,3^2$の値を求めます。この時たとえば$3^{1024}$であれば実際に$1023$回の掛け算を行う必要はなく

\begin{align}
3^{1024} &= {(3^{512})}^2 \\
3^{512} &= {(3^{256})}^2 \\
&\vdots \\
3^4 &= {(3^2)}^2 \\
3^2 &= {(3^1)}^2
\end{align}

というように計算すれば少ない掛け算の回数で求めることができます。最後に$3^{1030} = 3^{1024} \times 3^4 \times 3^2$を計算すれば終了です。たった十数回の掛け算で$3^{1030}$を求めることができました。今回は$3^{1030}$を例に使いましたが、この説明が理解できていれば数字を変えても同様の方法が使えることが分かるはずです。
　ここまで来ればフェルマーの小定理を使って導いた式を二分累乗法で高速に計算することで、二つの整数の商を$M$で割った余りを現実的な時間で求められることを理解していただけたかと思います。

最後に

　分かりにくい箇所も多々あるかと思いますので質問や提案等を頂ければできる限り改善していきたいと思っています。ご覧いただきありがとうございました。