用c++实现快速幂算法

快速幂算法（也称为二分幂算法）是一种在计算幂运算时，利用幂运算的特性，使得计算速度更快的算法。

C++代码实现如下：

#include<iostream>
using namespace std;
int pow(int a,int b,int mod)
//a是底数，b是指数，mod是模数
{
    int res=1;
    while(b>0)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    int a,b,mod;
    cin>>a>>b>>mod;
    cout<<pow(a,b,mod)<<endl;
    return 0;
}

在该代码中，我们使用了位运算来加速计算，将指数 b 转化为二进制后，每次将 a 的平方乘到结果 res 中，并将 b 右移一位。当 b 的最低位为 1 时，将 a 乘到结果 res 中。

这样可以在 O(log b) 的时间复杂度内完成计算，比起普通的暴力求幂的时间复杂度 O(b) 要快得多。