[C++知识库]c++ a^b

题目（来源：https://www.acwing.com/problem/content/91/）

求 a 的 b 次方对 p

取模的值。

输入格式

三个整数 a,b,p

,在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

0≤a,b≤109

1≤p≤109

输入样例：

3 2 7

输出样例：

2

?本题考察快速幂。这里初略的介绍一下快速幂

????????在计算7^n的时候，最容易想到的方法就是写成n个7相乘，这样的时间复杂度是o(n),如果多来几组数据，很有可能TLE。而使用快速幂则可以将时间复杂度降低到o(logn)。快速幂有2个版本：

1.递归快速幂

以2^10为例。

????????将2^10拆为2? ^ 5 * 2 ^ 5, 2 ^ 5里进行了4次乘法计算，2 ^ 5 * 2 * 5进行了一次乘法运算，这样就想原先的9次运算降低为5次运算。

??????? 对于2 ^ 5,继续对半拆分，写成2 ^ 2 * 2 ^ 2 * 2,这样2 ^ 5 就只需要进行3次运算。

由此可见，可以得出递归方程：如 a ^ n 中

转化为代码：
?

int qpow(int a, int n)
{
    if(n == 0)
        return 1;
    else if(n % 2)//n是奇数
        return qpow(a, n - 1) * a;
    else //n是偶数
    {
         int temp = qpow(a, n / 2);
         return temp * temp;
    }
}

?2.迭代快速幂

????????还是以2 ^ 10为例，将10转换为二进制数1010，由于二进制数的特殊性，二进制数1010等于二进制数1000和二进制数0010，这样2 ^ 10 = 2 ^ (1010) = 2 ^ ( 0010 + 1000) = 2 ^0010 * 2 ^ 1000 = 2 ^ 2 * 2 ^ 8。

转换成代码：

int qpow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

题目ac代码

#include<iostream>

using namespace std;

typedef long long LL;

int a, b, mod;


int qpow(LL a, int n)
{
    LL ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

int main()
{
    cin >> a >> b >> mod;
    
    cout << qpow(a, b) % mod;

    return 0;
}

注意事项：这里的a和ans应该声明为long long，应为在语句a = a * a % mod语句中，a * a 最大为10^18,mod可能取1，这样如果a为int，就会超过数据范围，返回1。

参考文章：https://zhuanlan.zhihu.com/p/95902286