快速幂

计算 $a^k$ mod $p$ 。

思路

将 $k$ 看成二进制数，则可由若干个 $2^d$ 组合而成；

预处理出$a^1$ $a^2$ $a^4$ … $a^k$；

然后组合出$a^b$即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef long long LL;

int a,b,p;
int t;

int qmi(int a,int b,int p) {
    LL res = 1 % p;
    while(b) {
        if(b & 1) res = (LL)res * a % p;    //如果此位为1，则需要组合
        a = (LL) a * a % p;
        b >>= 1;
    }
    return res;
}