简介

快速幂求余算法是一种可以在O(logn)下求出ab mod c的一种算法。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

具体实现

需要用到的定理：
快速幂求余 随笔

上面的公式，使得原本需要用a的b次方才能取得的余数，现在远远小于b的次方就可以求得。

算法实现：

long long  PowerMod (int a, int b, int c) {
    int  ans = 1;
    a = a % c;
    while(b>0) {
        if(b % 2 = = 1) //b为奇数
            ans = (ans * a) % c;
        b = b/2;       //   b>>=1;
        a = (a * a) % c;
    }
    return ans;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄