繰り返し二乗法


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

繰り返し二乗法

解説

0を含むすべて自然数は2のべき乗の和の組み合わせで表すことが出来る。2進数がその例である。

nを2のべき乗の和で表すと

n = 2^(k_1) + 2^(k_2) + 2^(k_3) + ...

よって、

x^n = x^(2^k_1) x^(2^k_2) x^(2^k_3) ...

2進数で操作をすればよいので1のビットが立つ部分iについて、resにx^iを掛けていく。

下位ビットから考えているのでxは順次二乗していけばよい。nの1と0のビットの数だけ処理するのみなのでO(log n)でxのべき乗を高速に求められる。

typedef long long ll;

ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while(n > 0) {
    if(n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}