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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "math/combinatorics/mod-pow.hpp"

概要

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

使い方

• mod_pow(x, n, p): $x^n \bmod p$ を返す.

計算量

• $O(\log n)$

Required by

• 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

/**
 * @brief Mod Pow(べき乗)
 *
 */
template <typename T>
T mod_pow(T x, 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 1 "math/combinatorics/mod-pow.hpp"
/**
 * @brief Mod Pow(べき乗)
 *
 */
template <typename T>
T mod_pow(T x, 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