快速幂

即求 \(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://hs-blog.axell.top/archives/11/