快速幂

Author Avatar
Axell 8月 26, 2018
  • 在其它设备中阅读本文章

快速幂

即求 \(x^m mod p\) 的值 (\(m>=10^8\)) , 此时常规运算会超出时间限制

二进制分解

代码

int pow(int a,int b,int c){
    int ans=1,tmp=a%c;
    while (b!=0){
        if (b&1)
            ans=((tmp%c)*(ans%c))%c;
            tmp=((tmp%c)*(tmp%c))%c;
            b/=2;
    }
    return ans%c;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。

本文链接:https://axell.wind-flower.cn/archives/11/