title: 快速幂
date: 2022-10-05 17:31:57

概念：

快速幂降低了时间复杂度，将指数转换为二进制计算

\(2^3\) ->\(2^{2^1}\times2^{2^0}\)

时间复杂度

• O(logN)
• 如果正常计算是for循环N次

代码实现

int fast_power(int a,int b,int mod){//a^b次
    int ans = 1;
    while(b){
        if(b&1){
            ans = a*ans%mod;
        }
        b>=1;
        a=a*a%mod;
    }
    return ans;
}