2X岁，是学生です

0%

快速幂

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

快速幂

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
27
28
29
30
#include <iostream>
using namespace std;

int qmi(int ai, int bi, int pi)
{
	long long res = 1;
	while (bi)
	{
		if (bi & 1)//位与，判断当前最低位是否为1
			res = res * ai % pi;
		ai = (long long) ai * ai % pi;
		//根据公式推到，a^k被拆分，
		//且后一个ai值为当前值的平方（bi被当作二进制数处理的原因）
		bi >>= 1;
	}
	return res;
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int ai, bi, pi;
		scanf("%d%d%d", &ai, &bi, &pi);
		printf("%d\n", qmi(ai, bi, pi));
	}
	return 0;
}

快速幂求逆元

快速幂也可以用于求解逆元。原理为费马定理：若n为质数，整数a不是n的倍数，。

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
27
28
29
30
31
32
#include <iostream>
using namespace std;

int qmi(int ai, int bi, int pi)
{
	long long res = 1;
	while (bi)
	{
		if (bi & 1)
			res = res * ai%pi;
		bi >>= 1;
		ai = (long long)ai*ai%pi;
	}
	return res;
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int ai, pi;
		scanf("%d%d", &ai, &pi);
		int res = qmi(ai, pi - 2, pi);
		if (ai%pi)
			printf("%lld\n", res);
		else
			puts("impossible");
	}
	return 0;
}