快速幂·学习笔记

快速幂是一个在O(log₂n)的时间内计算a^b的技巧，相比直接暴力计算O(n)的时间复杂度快了许多。

原理

在计算a^b的时候，将b转换为k_n*2ⁿ+k_n-1*2^n-1+……+k₂*2²+k₁*2¹+k₀*2⁰（k_n，k_n-1，……k₂，k₁，k₀取0或1），运用a^(m+n)=a^m·aⁿ

所以a^b=a^{（k_n*2n+k_n-1*2n-1+……+k₂*22+k₁*21+k₀*20）}=k_na^{2^n}+k_n-1a^{2^n-1}+……+k₂a^{2^2}+k₁a^{2^1}+k₀a^{2^0}

例：a¹³=a^(1101)₂=a⁸·a⁴·a^1•

代码

#include<bits/stdc++.h>
using namespace std;
long long a,b;
int main(){
    cin>>a>>b;
    long long n=a,ans=1;
    while(b!=0){
        if(b&1==1){//判断b转二进制末尾是否为1
            ans=ans*n;
        }
        n=n*n//n每次平方 由一次方变为平方，再变为四次方，八次方
        b=b>>1；
    }
    cout<<ans;
    return 0;
}

 注意事项

ans，n均以指数增长，有时取模，有时要用long long或高精度