Processing math: 100%

快速幂&快速乘法取模模板

发表于 更新于 分类于
本文字数： 766 阅读时长 ≈ 1 分钟

快速乘法取模：O(logb)

举个栗子：3×11=3×(1011)2=3×[(1000)2+(000)2+(10)2+(1)2]
=3×[8+0+2+1]=33。

1
2
3
4
5
6
7
8
9
LL quick_mul(LL a, LL b, LL mod){  
    LL res = 0LL; //注意初始值为0
    while(b) {
        if(b & 1) res =(res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}
复制

快速幂取模：O(logb)

举个栗子：311=3(1011)2=3(1000)2×3(000)2×3(10)2×3(1)2=38×30×32×31

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LL quick_mul(LL a, LL b, LL mod){  //快速乘法取模
    LL res = 0LL; //注意初始值为0
    while(b) {
        if(b & 1) res =(res + a) % mod;
        a = (a + a) % mod; //每次扩大2倍
        b >>= 1;
    }
    return res;
}
LL quick_mod(LL a, LL b, LL mod) { //快速幂取模
    LL res = 1LL; //注意初始值为1
    while(b) {
        if(b & 1) res = quick_mul(res, a, mod);
        // res = res * a % mod;
        a = quick_mul(a, a, mod);
        //a = a * a % mod;
        b >>= 1;
    }
    return res;
}
复制
0%