逆元を求める方法

競技プログラミングやLeetCodeの問題を解いていると、「とある素数で割ったあまりを求めなさい」というタイプの出題をよく見かけます。このような問題では、逆元が必要になる場合があります。

たとえばJavaのように、逆元を求めるライブラリが標準に用意されている場合は、それを利用するのが一番簡単です。

public static long MOD = 1_000_000_000 + 7;

public long modinv(long x) {
  return BigInteger.valueOf(x).modInverse(BigInteger.valueOf(MOD)).longValue();
}

逆元を求めるAPIが用意されていない場合でも、べき乗のあまり(modpow)を求めるライブラリが用意されている場合は、これを利用します。たとえばPythonなどがそうです。

MOD = 10**9+7

def modinv(x):
    return pow(x, MOD - 2, MOD)

逆元とべき乗のあまりのどちらも標準で用意されていないのであれば、自分で用意するほかありません。以下はRustの例です。

const MOD: i128 = 1_000_000_000 + 7;

fn modinv(a: i128) -> i128 {
     modpow(a, MOD - 2)
 }
 
 fn modpow(base: i128, exp: i128) -> i128 {
     if exp == 0 {
         return 1;
     }
     if exp % 2 == 0 {
         modpow((base * base) % MOD, exp / 2)
     } else {
         (modpow(base, exp - 1) * base) % MOD
     }
 }

環境情報

• javac 21.0.6
• Python 3.8.10
• rustc 1.83.0 (90b35a623 2024-11-26)