二分累乗法
$ 3^{64}を求めたくなったとする。普通にforループを使って累乗を計算すると3を64回掛けないといけない。
$ 3^1
$ 3^2
$ 3^3
$ 3^4
$ 3^5
$ 3^6
︙
$ 3^{64}
計算量的に$ O(N)かかる。実はこれを$ O(log N)に改良するテクがある。
$ 3^{1}
$ 3^{1}×3^{1} = 3^{2}
$ 3^{2} × 3^{2} = 3^{4}
$ 3^{4} × 3^{4} = 3^{16}
$ 3^{16} × 3^{16} = 3^{32}
$ 3^{32} × 3^{32} =3^{64}
なんか少ない。よく分からんけど、さっき求めたやつ同士を掛けることで右上の数が$ 2^nの速さで増えていってる。
でもなんかこれだと2の累乗したやつしか作れなさそう…→実は作れる
$ 3^{45}を作りたい
さっきの方法で素早く求められるのは$ 3^{1},3^{2},3^{4},3^{16},3^{32}だけ
実は$ 3^{45} = 3^{32}×3^{8}×3^{4}×3^{1}になる
二進法表記したときに$ 45 = 101101_{(2)}になるので…
https://gyazo.com/6ac21d22c90f8763dd0e6aa6368910d0
このコードを解読しながら実際にライブラリを作ってみると分かりやすいと思います(bit演算が出てくる)。 code:二分累乗法(modあり).cpp
// aのb乗(MODした)を返す。
ll modpow(ll a, ll b, ll mod = 1000000007) {
ll res = 1;
for (a %= mod; b; a = a * a % mod, b >>= 1)
if (b & 1) res = res * a % mod;
return res;
}