繰り返し二乗法
繰り返し二乗法のアルゴリズムを答えよ。
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; }