快速幂

1.快速幂

快速幂的核心：反复平方法

快速幂即快速的求出 $a^kmodp$ 的结果，可以在 $O(logk)$ 的时间复杂度内求出结果，其中满足 $1≤a,p,k≤10^9$，

image-20230407183431632

image-20230407203436115

1
2
3
4
5
//暴力法O(k)
res = 1;
for (int i = 1; i <= k; ++i) {
    res = res * a % p;
}
1
2
3
4
5
6
7
8
//快速幂O(logk)
int res = 1;
while (k) {
    if (k & 1) res = (long long)res * a % p;
    k >>= 1;//最后一位抹去
    a = (long long)a * a % p;
}
return res;

1.AcWing875.快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

//a^k % p
int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = (long long)res * a % p;
        k >>= 1;//最后一位抹去
        a = (long long)a * a % p;
    }
    return res;
}

int main() {
    int m;
    scanf("%d", &m);
    while (m--) {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}

2.AcWing876.快速幂求逆元

  • 考察：费马定理与快速幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
using namespace std;

//a^k % p
int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = (long long)res * a % p;
        k >>= 1;//最后一位抹去
        a = (long long)a * a % p;
    }
    return res;
}

int main() {
    int m;
    scanf("%d", &m);
    while (m--) {
        int a, p;
        scanf("%d%d", &a, &p);
        int res = qmi(a, p - 2, p);
        if (a % p) printf("%d\n", res);//res != 0 表示a不是p的倍数
        else puts("impossible");//a是p的倍数
    }
    return 0;
}