Mod Pow (べき乗) (math/combinatorics/mod-pow.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 07:26:44+00:00
• Include: #include "math/combinatorics/mod-pow.hpp"

ある値のべき乗を求める。

mod_pow

T mod_pow(T x, int64_t n, const T& p)

$x^n \bmod p$ を返す。

計算量

• $O(\log n)$

Required by

• Mod Sqrt (math/combinatorics/mod-sqrt.hpp)
• Mod Tetration (テトレーション) (math/combinatorics/mod-tetration.hpp)

Verified with

• test/verify/aoj-ntl-1-b.test.cpp
• test/verify/yosupo-sqrt-mod.test.cpp
• test/verify/yosupo-sqrt-of-formal-power-series.test.cpp
• test/verify/yosupo-tetration-mod.test.cpp

Code

#pragma once

#include <cstdint>

/**
 * @brief Mod Pow(べき乗)
 *
 */
template <typename T>
T mod_pow(T x, std::int64_t n, const T& p) {
  T ret = 1;
  while (n > 0) {
    if (n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret % p;
}

#line 2 "math/combinatorics/mod-pow.hpp"

#include <cstdint>

/**
 * @brief Mod Pow(べき乗)
 *
 */
template <typename T>
T mod_pow(T x, std::int64_t n, const T& p) {
  T ret = 1;
  while (n > 0) {
    if (n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret % p;
}

Back to top page