Modular exponentiation （べき乗 mod）
(number/pow_mod.hpp)

• View this file on GitHub
• Last update: 2026-04-11 14:52:31+09:00
• Include: #include "number/pow_mod.hpp"

整数 $x$, 非負整数 $n$, 正整数 $m$ に対し，$x^n \bmod m$ を $O(\log n)$ で計算する．繰り返し二乗法による実装．Int が int のとき内部で long long，long long のとき __int128 を用いてオーバーフローを回避する．

使用方法

int a = pow_mod(3, 100, 1000000007);       // Int = int
long long b = pow_mod(3LL, 100LL, (long long)1e18 + 9); // Int = long long

• x: 底．
• n: 指数（$n \ge 0$）．
• md: 法（$m \ge 1$）．$m = 1$ のとき常に $0$ を返す．

Required by

• Primitive root modulo $n$ （原始根の発見） (number/primitive_root.hpp)

Verified with

• number/test/primitive_root.test.cpp
• number/test/primitive_root_1e18.test.cpp

Code

#pragma once
#include <cassert>
#include <type_traits>

template <class Int> Int pow_mod(Int x, long long n, Int md) {
    using Long =
        std::conditional_t<std::is_same_v<Int, int>, long long,
                           std::conditional_t<std::is_same_v<Int, long long>, __int128, void>>;
    assert(n >= 0 and md > 0);
    if (md == 1) return 0;
    if (n == 0) return 1;

    x = (x % md + md) % md;
    Int ans = 1;
    while (n > 0) {
        if (n & 1) ans = (Long)ans * x % md;
        x = (Long)x * x % md;
        n >>= 1;
    }
    return ans;
}

#line 2 "number/pow_mod.hpp"
#include <cassert>
#include <type_traits>

template <class Int> Int pow_mod(Int x, long long n, Int md) {
    using Long =
        std::conditional_t<std::is_same_v<Int, int>, long long,
                           std::conditional_t<std::is_same_v<Int, long long>, __int128, void>>;
    assert(n >= 0 and md > 0);
    if (md == 1) return 0;
    if (n == 0) return 1;

    x = (x % md + md) % md;
    Int ans = 1;
    while (n > 0) {
        if (n & 1) ans = (Long)ans * x % md;
        x = (Long)x * x % md;
        n >>= 1;
    }
    return ans;
}

Back to top page