数论——快速幂

快速幂

1. 定义：
   顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。
2. 举例：
   计算: $a^{k}modp$
   假设k = 5，转化为二进制即101，又有这样的性质
   则 $a^{5}modp=a^{101}modp=[(a^{2^2}\mathrm{mod}p)\ast (a^{2^0}\mathrm{mod}p)]modp$
   起始：res = 1， a = a
   对于二进制101 ，每次查看末位是1还是0，遇到1则res = res * a mod p。每次移一位，且a = a * a % p

例题

给定 n 组 ai,bi,pi，对于每组数据，求出 abiimodpi 的值。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含三个整数 ai,bi,pi。

输出格式
对于每组数据，输出一个结果，表示 abiimodpi 的值。

每个结果占一行。

数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×10^9
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1

n = int(input())

def qmi(a, k, p) :
	res = 1
	while k :
		if k & 1 :
			res = res * a % p
		k >>= 1
		a = a * a % p
	return res % p #防止k=0，p等于1的情况

for i in range(n) :
	a, b, p = map(int, input().split())
	print(qmi(a, b, p))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 0∼p−1 之间的逆元。

乘法逆元的定义
若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a×x(modm)，则称 x 为 b 的模 m 乘法逆元，记为 b−1(modm)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，bm−2 即为 b 的乘法逆元。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一个数组 ai,pi，数据保证 pi 是质数。

输出格式
输出共 n 行，每组数据输出一个结果，每个结果占一行。

若 ai 模 pi 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。

数据范围
1≤n≤105,
1≤ai,pi≤2∗109
输入样例：
3
4 3
8 5
6 3
输出样例：
1
2
impossible

概念讲解

1. 乘法逆元：整数a，若$a\ast a^{-1}\equiv 1(\mathrm{mod}p)$，称$a^{-1}$为模p的乘法逆元
2. 费马小定理：费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有$a^{（p-1）}\equiv 1（modp）$

因为题目中说明p为质数，所以a的逆元$a^{-1}=a^{p-2}$

n = int(input())

def qmi(a, k, p) :
	res = 1
	while k :
		if k & 1 :
			res = res * a % p
		k >>= 1
		a = a * a % p
	return res

for i in range(n) :
	a, p = map(int, input().split())
	if a % p == 0 :
		print("impossible")
	else :
		print(qmi(a, p - 2, p))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结

快速幂可以快速的求出指数运算，通过和费马小定理的配合也能更加简洁的求出一个数的逆元，但要注意条件哦。