ただし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; }
なるほどー。
適当に書いたプログラムなので、オーバーフローを全然考慮していないので要注意。