べき乗(Mod-Pow)

説明

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

計算量

• $O(\log n)$

実装例

• power($x$, $n$, $mod$):= $x^n$ を $mod$ で割った余りで返す。

template< typename T >
T mod_pow(T x, T n, const T &p) {
  T ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret;
}

検証

AOJ NTL_1_B べき乗

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B"

#include "../../template/template.cpp"

#include "../mod-pow.cpp"

int main() {
  int64 M, N;
  cin >> M >> N;
  cout << mod_pow(M, N, (int64)(1e9 + 7)) << endl;
}