mod 上での累乗 / 繰り返し二乗法
高速な累乗計算のための必須テク。
累乗
本質的には$ n^kは$ nを$ k回かけることになるので、ただの掛け算と同値であり、$ \mathrm{mod}を積極的に取ればよい。
だが、この計算は$ \Omicron(k)かかるので、例えば$ 10^{18}乗を求めたいことが往々にしてあるが、ナイーブな実装では遅すぎてできない。
繰り返し二乗法
例えば$ n^6 = n^4 \times n^2である。指数が大きくなっても、指数を何らかの和の形で表現してその積を出せば良さそうだ。
なお、一般に$ n^a + n^b = n^{a+b}である。
指数を何らかの整数の和に分解する。するとすれば、$ 2の冪乗だろう。
なぜなら、n << 1と書くと$ n^2を得られるからだ。これを繰り返せば$ n, n^2, n^4, n^8, \ldotsを得られる。
指数を$ 2の冪乗に分解すること、これは$ 2進数で表すことに等しい。
$ 2進数で$ 1であるような桁について対応する$ n^{(2^v)}をかけ続ければいいので、以下のようなプログラムで高速に累乗を計算できる。
code:cpp
long long modpow(long long n, long long k, long long mod){
long long res = 1;
while(k){
if(k & 1){
res = (res * n) % mod;
}
n = (n * n) % mod;
k >>= 1;
}
return res;
}
計算量は大幅に高速になって$ \Omicron(\log{k})となる。
これだけ高速になれば十分実用に足るだろう。これでも遅いなら$ n^{(4^v)} \times 1, 2, 3のテーブルを作って$ 4進数とかで管理してください(速くならなさそう)。
型の最大、最小値を超えないなら mod を外しても良い。
なお、Python では mod を指定してpowを使うと勝手にこれになるらしい。