MOD Fermatの小定理
(library/number/mod/mod_inverse.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/number/mod/mod_inverse.hpp"

MOD Fermatの小定理

できること

• MOD下で、逆元を求める

計算量

$O(logM)$

使い方

long long inv = mod_inverse(a, MOD);

Depends on

• MOD 二分累乗 (library/number/mod/mod_pow.hpp)

Required by

• MOD 組み合わせ nCk (library/number/mod/mod_combination.hpp)

Verified with

• MOD 組み合わせ nCkのテスト (tests/number.mod.mod_combination.test.cpp)

Code

#pragma once
#include "library/number/mod/mod_pow.hpp"
long long mod_inverse(long long a, long long m) { return mod_pow(a, m - 2, m); }

#line 2 "library/number/mod/mod_pow.hpp"
long long mod_pow(long long a, long long n, long long m) {
    long long res = 1ll;
    while (n > 0) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1ll;
    }
    return res;
}
#line 3 "library/number/mod/mod_inverse.hpp"
long long mod_inverse(long long a, long long m) { return mod_pow(a, m - 2, m); }

Back to top page