这题是非常经典的快速幂算法！

 推荐一篇快速幂学习的博客，讲的非常循序渐进且详细：快速幂学习

以下是一些自己的理解，可以帮助快速入门

无模版本

快速幂算法，核心思想就是二分思想（所以复杂度为O(logN)），把幂逐步减半，减少计算时间。

若计算a^n：

• n为偶数，a^n=a^(n/2)*a^(n/2)
• n为奇数，a^n=a^(n-1)*a，相当于把奇数变为偶数，再计算

对应核心代码：

long long int qpow(long long a, long long n)
{
    long long ans = 1;
    while (n)
    {
        if (n % 2 == 1) //指数是奇数，先做一步乘法，化成偶数
        {
            ans = ans * a;//这里可以理解为，每次遇到奇数幂，就把计算结果的一部分暂存进ans（另一部分是下面的a*a）。到最后n==1时，就把全部的结果都存进ans了。如果实在理解不了，非常建议用纸笔画一遍流程。就能理解了        }
        //偶数不做单独处理，是因为int强制类型转换。即当n为奇数，n/2和（n-1）/2的结果是一样的
        a = a * a;
        n = n / 2;
    }
    return ans;
}

有模版本

• 首先明白求模运算优先级：与乘法、除法相同，小于幂。所以代码里面是先计算乘法，再求模
• 其次就是求模运算的规则：(a*b)%p=((a%p) * (b%p))%p
• 核心思想：每做一次乘法去一次模，最后对返回结果再取一次模

对应核心代码：

long long int qpow_mod(long long a, long long n)
{

    long long ans = 1;
    a = a % MOD; //按照运算法则，这一步是必须的，防止a>mod的情况出现。补全这个才算满足了上面的分配率
    //while中，因为a和ans都是保证小于MOD的（a...