べき乗の計算回数を少なくする繰り返し自乗法

べき乗の計算回数を少なくする方法をAIZU_ONLINE_JUDGEのNTL_1_B:Powerを用いて求めたいと思います。

問題

2つの整数m,nについて、m^nを1000000007で割った余りを求めてください。

単純に計算すると、時間がオーバーしてしまうので、計算方法を工夫する必要があります。
計算方法は

$x^n = (x^2)^\frac{n}{2}$

であることを利用します。

べき乗を計算する関数をpowとして、以下のように再帰関数として定義することで
計算回数を減らします。

pow(x,n) = 1(nが0の時)
pow(x,n) = $pow(x^2,n ÷ 2)$(nが偶数の時)
pow(x,n) = $pow(x^2,n ÷ 2) × x$(nが奇数の時)

例として、この関数を$2^{11}$でトレースしてみます。

$2^{11} = (2 × 2)^5 × 2$(nが奇数のケース)

$4^5 = (4 × 4)^2 × 4$(nが奇数のケース)

$16^2 = (16 * 16)^1$(nが偶数のケース)

このように計算回数を3回に減らすことができました。

Order記法

繰り返し自乗法は、再帰関数の引数が半分になっていくので、
O(logn)のアルゴリズムになります。

以上を踏まえての全体のプログラムです。

#include <iostream>
#include <cmath>

using namespace std;

long pow(long x,long n,long M){
    long res = 1;
    if(n > 0){
        res = pow(x,n / 2,M);
        if(n % 2 == 0){
            res = (res * res) % M;
        }else{
            res = (((res * res) % M) * x) % M;
        }
    }
    return res;
}

int main(){
    int m,n;
    cin >> m >> n;
    
    cout << pow(m,n,1000000007) << endl;
    return 0;
}