参考
「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 - Qiita
分かりやすいmodの説明動画
基本
- 掛け算、足し算、引き算は、計算途中で余りだす。
- 引き算は、余りがマイナスになったらmodを足す。
- 割り算は計算途中で余り出すのが通用しない。
- 割り算は、逆元を出して、掛け算に変換する。
逆元
- モジュラ逆数ともいうっぽい。
- mod世界の逆数的な感じ。
- 上記の式を満たすxのこと。
- 例えば、mod 13の場合、1/7の逆元は2です。
- 56 ÷ 7を13で割った余りを出すときに、56 x 2を考えればよくなります。
逆元の求め方
1/a ≡ x (mod m)
は、ax ≡ 1 (mod m)
に変換できます。- 上記は、
ax = my + 1
になるということです。 - 変形すると、
ax + my = 1
にできます。 - aとmが互いに素であれば、整数x, yのペアが存在します。
- xの出し方は、拡張ユークリッド互除法が使えます。
サンプルコード
#include <bits/stdc++.h> using namespace std; using LL = long long; LL extgcd(LL a, LL b, LL &x, LL &y) { if (b == 0) { x = 1; y = 0; return a; } LL gcd = extgcd(b, a % b, x, y); LL oldX = x; x = y; y = oldX - a / b * y; return gcd; } LL modinv(LL a, LL m) { LL x, y; extgcd(a, m, x, y); return x; } int main() { LL a = 7, b = 13; LL x = modinv(a, b); cout << x << endl; }
結果
2