Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

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

概要

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

使い方

計算量

Required by

Verified with

Code

/**
 * @brief Mod Pow(べき乗)
 * @docs docs/mod-pow.md
 */
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(べき乗)
 * @docs docs/mod-pow.md
 */
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