ei1333's page

ホーム > Wiki

繰り返し二乗法

説明

冪乗を高速に求めるアルゴリズム。すべての自然数は $2$ の冪乗和の組み合わせで表すことができるという性質を利用している。 $N$ を $2$ の冪乗和で表すと $N = 2^{K_1} + 2^{K_2} + 2^{K_3} + \dots$ となる。よって $x^N = x^{2^{K_1}} \times x^{2^{K_2}} \times x^{2^{K^3}} \times \dots$。$2$ 進数で操作すればよいので, $1$ のビットが立つ部分 $i$ について, 解に $x^i$ を掛けていく。

計算量

$O(\log N)$

実装例

template< typename T = long long >
T pow_mod(T x, T n, T mod)
{
  T ret = 1;
  while(n > 0) {
    if(n & 1) ret = 1LL * ret * x % mod;
    x = 1LL * x * x % mod;
    n >>= 1;
  }
  return ret;
}

問題例