mのn乗をO(log n)で計算する

ただしmは整数、nは非負の整数。
こんな感じでやればO(log n)でm^nが計算できる。

#include <iostream>
using namespace std;

int pow(int m, int n) {
    if (n == 0) { return 1; }
    if (n % 2 == 0) { return pow(m*m, n/2); }
    return pow(m, n-1) * m;
}

int main() {
    cout << pow(2, 16) << endl;
}

なるほどー。
適当に書いたプログラムなので、オーバーフローを全然考慮していないので要注意。