繰り返し二乗法

計算量

$a^n$ を $O(\log n)$ で求めることができます。

普通に計算しようとすると $a$ を $n$ 回かけるので、 $O(n)$ かかります。

仕組み

例として $3^{13}$ を解いてみましょう。

理由はこれから述べますが繰り返し二乗法ではまず、指数を二進数に変換します。
今回だと $n = 13$ なので

$13_{(10)} = 1101_{(2)}$

となりますね。
これをさらに

$13_{(10)} = 1101_{(2)} = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$

と変換します。

これを指数に使うと

$a^{13} = a^{8+4+1} = a^8 × a^4 × a^1$

このようにして2の累乗の形に変換できました。

そして $a^8 × a^4 × a^1$ は、前の値を二乗するだけで求まります。
つまり、二進数化した後にその桁数分ループを回し、ループごとに $a$ に $a$ をかけていく。1が立っていれば答えに今の $a$ をかけてあげることで計算量を落としつつ結果を得られるということです。
文字だけ見てもあれなので、この後に載せるコード例を見ると想像つきやすいと思います。

一般に、 $n$ を2進数で表現したときその桁数は $\lfloor \log_{2}n \rfloor + 1$ であり、これがそのままループ数と対応するため $n$ 回の掛け算を $\log n$ 回に抑えることができます。

ll power(ll a, ll n) {
  ll result = 1;
  while (n > 0) {
    // nの最下位ビットが1ならresultに掛ける
    if (n & 1) result *= a;
    a *= a;
    // n を右シフトして次のビットへ
    n >>= 1;
  }
  return result;
}

実際には $a$ が大きな数になってしまうため $mod$ を取るような問題が多いです。
掛けるたびに $mod$ を取ってあげればいいですね(これは頻出テクニックです。知らなかった人は先に $mod$ のテクニックについて調べてください)。

例題

以下の例題を解いてみましょう。

問題文
$a^b$ を1000000007で割った余りを求めてください。

制約
$1 \leq a \leq 99$
$1 \leq b \leq 10^9$

$b$ が最大 $10^9$ なので、普通に $O(n)$ で計算しようとするとTLEします。繰り返し二乗法で $O(\log b)$ に落としましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll power(ll a, ll n, ll mod) {
  ll result = 1;
  a %= mod;
  while (n > 0) {
    if (n & 1) result = result * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return result;
}

int main() {
  ll a, b;
  cin >> a >> b;
  cout << power(a, b, MOD) << endl;
  return 0;
}

掛け算をするたびに% modを取っています。result * aの前にresultは既にmod未満なので、オーバーフローを防ぐためにはaもmod未満であることが必要です。そのため最初にa %= modとしています。

その他の例題

まとめ

指数が大きいときの累乗計算は繰り返し二乗法が基本です。
難しい内容でもなくこのアルゴリズムだけで解けるような問題だとAtCoderではB、C辺りで頻出なので、オーバーフローを起こして爆死することのないよう知っておくといいでしょう。
もしくはpythonを使いましょう(メモリが許す限り桁が無限なので)。