整数累乗 (mod) (Math/mod_power.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-04-13 19:22:19+09:00
• Include: #include "Math/mod_power.hpp"

mod_pow

T  mod_pow(T x, T n, T mod)

繰り返し二乗法によりmodを法としたときのx^nを計算して返します。

制約

• $ 0 \leq n$
• $ 0 < \text{mod}$
• $ \text{mod}^2 \leq \text{型Tの最大値}$

計算量

• $O(\log n)$

Depends on

• 繰り返し二乗法 (Other/fast_power.hpp)

Required by

• 高速素因数分解 (Math/fast_factorizer.hpp)
• 素数判定 (Math/primality_test.hpp)

Verified with

• test/Math/fast_factorize/yosupo-factorize.cpp
• test/Math/mod_power/aoj-NTL_1_B.cpp
• test/Math/mod_power/my_test.cpp
• test/Math/primality_test/yosupo-primality_test.cpp

Code

#include <bits/stdc++.h>
using namespace std;

#include "Other/fast_power.hpp"

template <typename T>
enable_if_t<is_integral_v<T> || is_same_v<T, __int128_t>, T>
mod_pow(T x, T n, T mod)
{
    assert(0 <= n);
    assert(0 < mod);
    assert(mod <= numeric_limits<T>::max() / mod);

    x %= mod;
    if (x < 0)
    {
        x += mod;
    }

    auto mul = [&](T a, T b) -> T
    {
        return (a * b) % mod;
    };

    auto e = [&]() -> T
    {
        return 1;
    };

    return fast_pow<T>(x, n, mul, e);
}

#line 1 "Math/mod_power.hpp"
#include <bits/stdc++.h>
using namespace std;

#line 2 "Other/fast_power.hpp"
using namespace std;

template <class S>
S fast_pow(S x, long long n, function<S(S, S)> mul, function<S()> e)
{
    assert(0 <= n);

    S ans = e();

    while (n)
    {
        if (n & 1)
        {
            ans = mul(ans, x);
        }
        x = mul(x, x);
        n >>= 1;
    }

    return ans;
}
#line 5 "Math/mod_power.hpp"

template <typename T>
enable_if_t<is_integral_v<T> || is_same_v<T, __int128_t>, T>
mod_pow(T x, T n, T mod)
{
    assert(0 <= n);
    assert(0 < mod);
    assert(mod <= numeric_limits<T>::max() / mod);

    x %= mod;
    if (x < 0)
    {
        x += mod;
    }

    auto mul = [&](T a, T b) -> T
    {
        return (a * b) % mod;
    };

    auto e = [&]() -> T
    {
        return 1;
    };

    return fast_pow<T>(x, n, mul, e);
}

Back to top page