【競プロ】逆元と剰余演算
ここでは、フェルマーの小定理を使って、剰余演算で逆元を求める計算について見ていきます。競プロ 記事の一覧はこちら。
逆元と剰余演算
【競プロ】フェルマーの小定理で見た内容を使って、商の剰余演算について見ていきます。この定理は次のような内容でした。
この式を変形すると、\[ a\cdot a^{p-2} \equiv 1 \pmod p \]となります。これは、 $\bmod p$ の世界では、 $a$ と $a^{p-2}$ を掛けると $1$ になる、ということです。
一般に、 $a$ にある値を掛けて $1$ になるとき、その値のことを $a$ の逆元(inverse element) といいます。逆数と似ていますが、逆数は数の掛け算での話をしているのに対し、逆元は $\bmod$ の世界も含めた、もっと広い世界での話をしています。逆元は、逆数を一般化したもの、ということもできます。
逆元と剰余演算の具体例
さて、ここからは具体的にコードを書いてみます。まず、次の問題を見てみましょう：AtCoder ABC F - Surrounded Nodes 。これを解くわけではありませんが、注記のところを見てみましょう。答えを有理数 $\dfrac{y}{x}$ の形にしてから、 $xz\equiv y \pmod {10^9+7}$ を満たす $z$ を答えなさい、となっていますね。これは要するに、 $x$ の逆元に $y$ を掛けたものを答えなさい、ということです。
続いて、入力例1・出力例1を見てみましょう。答えは $\dfrac{1}{8}$ だから $125000001$ を出力する、と書いていますね。これは、 $8$ の逆元が $125000001$ である、という意味です。この $125000001$ をどのようにして求めるのか、この計算だけを考えてみましょう。
【競プロ】素数と合成数などでも触れましたが、 $10^9+7$ は素数です。そのため、フェルマーの小定理から、 $x$ の逆元は $x^{10^9+7-2}$ であることがわかります。なので、例えば、 $8$ の逆元なら $8^{10^9+7-2} \pmod {10^9+7}$ を計算すればいいことがわかります。
ただ、少し難しい点が残っています。そのまま $10^9+7-2$ 乗を計算すると時間オーバーになってしまうんですね。そのため、そのまま掛けて答えを出すわけにはいきません。しかし、この問題をクリアする方法はすでに見ています。【競プロ】繰り返し二乗法と再帰関数で見たように、繰り返し二乗法を使えばいいですね。
以上から、正の整数を受け取って、 $\bmod {10^9+7}$ の世界での逆元を返すコードは次のように書くことができます。
#include <iostream>
using namespace std;
long long MOD = 1e9 + 7;
long long modPow(long long x, long long a) {
if (a == 1) return x;
if (a % 2) return (x * modPow(x, a - 1)) % MOD;
long long t = modPow(x, a / 2);
return (t * t) % MOD;
}
long long modInv(long long x) {
return modPow(x, MOD - 2);
}
int main() {
long long x; cin >> x;
cout << modInv(x);
return 0;
}x を受け取って、 $\bmod 10^9+7$ での逆元を返す modInv を使って答えを出力しています。 modInv は、フェルマーの小定理から、x の MOD - 2 乗を計算しています。
この MOD - 2 乗の計算は、modPow で行っています。a 乗を計算する際、1 なら x を返し、それ以外の奇数なら、1 と a - 1 に分けて計算しています。偶数乗であれば、a を半分にしてから同じものを2回掛ける、という処理をしています。こうして指数をどんどん減らしていくことで、高速に a 乗を計算できます。繰り返し二乗法を使った計算です。
実際に 8 を入力すれば、125000001 が返ってきます。こうして、 $\bmod 10^9+7$ での逆元を求めることができるようになりました。
おわりに
ここでは、剰余演算で逆元を求める方法について見てきました。フェルマーの小定理を使えば、 $a$ の逆元は $a^{p-2}$ となることがわかるので、これを繰り返し二乗法を用いて求めればいいのでした。ここで見た内容を応用すれば、別のページで見るように、 ${}_n\mathrm{C}_k$ を $10^9+7$ で割った余りを計算することもできるようになります。
