高速な累乗の計算 (paizaランク C 相当)

高速に累乗を計算する方法として、繰り返し二乗法というものがあります。
このアルゴリズムは、a の b 乗 (a ^ b) を、 a ^ (2 ^ i) 乗を用いて表すことで計算量を落とすアルゴリズムです。

まず b の ２ 進数表現を考えます。b の最下位の桁が １ かどうかを確認します。

最下位の桁が １ の場合、 a を ans にかけます。

この処理が終わったら、a を a の ２ 乗に置き換え、b を右に １ ビットシフト(割る 2)します。

これを b が 0 以下になるまで繰り返すことで、i 回目のときに、a ^ (2 ^ (i - 1)) のかけ算を行うことができます。

ex) 2^13の場合

2^13 = 2^8 * 2^4 * 2^1
13 = 1101(2)

１回目のループ

1101(2) & 1 = 1    ans = ans*2 ;        N>>1 = 110(2)

２回目のループ

110(2) & 1 = 0     ans = ans;           N>>1 = 11(2)

３回目のループ

11(2) & 1 = 1      ans = ans*(2^4);     N>>1 = 1(2)

４回目のループ

1(2) & 1 = 1       ans = ans*(2^8);     N>>1 = 0(2)

整数 A , B , M が与えられるので、 A^B(mod M) を求めましょう。