现在来认识一种新的求幂算法—快速幂算法。这个算法可以在O(logn)的时间复杂度下计算nm的值(要求m为自然数)。相比朴素O(n)累乘算法，效率大大提升。
        快速幂算法基于倍增思想，是倍增算法的一个应用。

        每一个自然数都可以写出它唯一的二进制数，即有:

        这里$0\leq k_1 < k_2< …< k_m$。
        那么$n^m$可以表示为$n^{2^{k_1}+2^{k_2}+…+2^{k_m}}$，即$n^{2^{k_1}} × n^{2^{k_2}} × … × n^{2^{k_m}}$，从而化为几个数的乘积，并且这几个数有这平方级的关系。这样就可以把求幂运算压至O(logn)复杂度。
        示例代码(答案对P取模):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>

using namespace std;

int main() {
    const int P = 10000007;
    long long int n, m;
    cin >> n >> m;
    long long int t = n;
    long long int ans = 1;
    while (m > 0) {
        if (m % 2 == 1)ans *= t, ans %= P;
        t *= t;
        t %= P;
        m /= 2;
    }
    cout << ans;
    return 0;
}