繰り返し二乗法（mod付き）
(algorithm/Math/ModularArithmetic/mod_pow.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Math/ModularArithmetic/mod_pow.hpp"

概要

自然数 $n, k, m$ に対して，

\[n^k \bmod m\]

を求める．

本実装では「繰り返し二乗法」を用いており，計算量は $\mathcal{O}(\log k)$ である．

問題

• “B - n^p mod m”. AtCoder Typical Contest 002. AtCoder. https://atcoder.jp/contests/atc002/tasks/atc002_b.

Verified with

• verify/aoj-NTL_1_B-mod_pow.test.cpp

Code

#ifndef ALGORITHM_MOD_POW_HPP
#define ALGORITHM_MOD_POW_HPP 1

#include <cassert>

namespace algorithm {

// 繰り返し二乗法（mod付き）．O(logK).
constexpr long long mod_pow(long long n, long long k, int mod) {
    assert(k >= 0);
    assert(mod >= 1);
    long long res = 1;
    n %= mod;
    while(k > 0) {
        if(k & 1LL) res = res * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return res;
}

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/ModularArithmetic/mod_pow.hpp"



#include <cassert>

namespace algorithm {

// 繰り返し二乗法（mod付き）．O(logK).
constexpr long long mod_pow(long long n, long long k, int mod) {
    assert(k >= 0);
    assert(mod >= 1);
    long long res = 1;
    n %= mod;
    while(k > 0) {
        if(k & 1LL) res = res * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return res;
}

}  // namespace algorithm

Back to top page