概要

\(X^N\) (mod \(M\))を高速に計算する。

計算量

\(O(\log N)\)

実装

using ll = long long;

ll fast_pow(ll x, ll n, ll m) {
  ll r = 1;
  while(n > 0) {
    if(n & 1) {
      r = (r * x) % m;
    }
    x = (x * x) % m;
    n >>= 1;
  }
  return r;
}

Verified

  • AOJ: "NTL_1_B: Elementary Number Theory - Power": source (C++, 0.00sec)

戻る