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

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

快速乘法取模：$O(log^b) $

举个栗子：
$ = 3 \times [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(log^b) $

举个栗子：$3^{11} = 3^{(1011)_2}=3^{(1000)_2}\times 3^{(000)_2}\times 3^{(10)_2} \times 3^{(1)_2}= 3^8\times 3^0\times 3^2\times 3^1$

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%