快速幂

快速幂

Axell Aug 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;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/11/