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

• View this file on GitHub
• Last update: 2026-01-15 10:11:56+09:00
• Include: #include "library/number/mod/mod_pow.hpp"

MOD 二分累乗

できること

• MOD下で、 $a^n$ を求める

計算量

$O(logN)$

使い方

long long ans = mod_pow(a, n, MOD);

Required by

• MOD 組み合わせ nCk (library/number/mod/mod_combination.hpp)
• MOD Fermatの小定理 (library/number/mod/mod_inverse.hpp)
• テトレーション (library/number/mod/mod_tetration.hpp)

Verified with

• MOD 組み合わせ nCkのテスト (tests/number.mod.mod_combination.test.cpp)
• MOD テトレーションのテスト (tests/number.mod.mod_tetration.test.cpp)

Code

#pragma once
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 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;
}

Back to top page