快速幂模板

递归算法

long long quick_pow(int x,int y){
    if (y==1) return x; 
    else if (y%2==0) return (int)pow(quick_pow(x,y>>1),2)%1000;
    else return (int)pow(quick_pow(x,y>>1),2)*x%1000;
}

非递归算法

long long quick_pow(int x,int y){
    int ans=1;
    x%=mod;
    while(y!=0){
        if (y&1) ans=(ans*x)%mod;
        y>>=1;
        x=x*x%mod;
    }
    return ans;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容