费马小定理

快速幂

理论

$a^n=a\times a\times \cdots \times a$，暴力的计算需要 O(n) 的时间。
快速幂使用二进制拆分和倍增思想，仅需要 O(logn) 的时间。

对 n 做二进制拆分，例如，$3^{13}=3^{(1101{)}_2}=3^8\cdot 3^4\cdot 3^1$，
对 a 做平方倍增，例如，$3^1,3^2,3^4,3^8\cdots \cdots$。

n 有 logn + 1个二进制位，知道了$a^1,a^2,a^4,a^8,\cdots ,a^{2^{\text{logn}}}$后，只需要计算 logn + 1 次乘法就可以了。

快速幂可以应用在任何具有结合律的运算中，例如，取模运算、矩阵乘法等。

例如， $(3^{13})\%p=((3^8)\%p\cdot (3^4)\%p\cdot (3^1)\%p)\%p$

模板

int quickpow(int a, int n) {
	int res = 1;
	while (n) {
		if (n & 1) {
			res = res * a;
		}
		a = a * a;
		n >>= 1;
	}
	return res;
}

例题

P1226 【模板】快速幂
题目描述
给你三个整数 $a,b,p$，求 $a^b\mathrm{mod}p$。

输入格式
输入只有一行三个整数，分别代表 $a,b,p$。

输出格式
输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

输入输出样例 #1

输入 #1

2 10 9

输出 #1

2^10 mod 9=7

说明/提示
样例解释

$2^{10}=1024$，$1024\mathrm{mod}9=7$。

数据规模与约定
对于 $100\%$ 的数据，保证 $0\le a,b<2^{31}$，$a+b>0$，$2\le p<2^{31}$。

#include<bits/stdc++.h>
using namespace std;
int quickpow(long long a, long long b, long long p) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res = res * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int main() {
	long long  a, b, p;
	cin >> a >> b >> p;
	cout << a << "^" << b << " mod " << p << "=" << quickpow(a, b, p);
	return 0;
}

理论

同余式
如果两整数a, b模m的余数相同，则称a, b模m同余，记为a ≡ b (mod m) 。例：8 ≡ 2 (mod 3)

乘法逆元
若a, b互质，且满足同余方程ax ≡ 1 (mod b)，则称x为a模b的乘法逆元，记作a⁻¹
例：8x ≡ 1 (mod 5)，解得x = 2, 7, 12…

费马小定理
若p为质数，且a, p互质，则a^(p - 1) ≡ 1 (mod p)
例：4^(3 - 1) ≡ 1 (mod 3)

证明
构造一个与p互质的序列A = {1, 2, 3, …, p - 1}，现在来证明：∏(i = 1)^(p - 1) a × Ai ≡ ∏(i = 1)^(p - 1) Ai (mod p)
每个a × Ai (mod p)的余数必是独一无二的，且a × Ai (mod p) < p ，则必与Ai (mod p)的余数集合相同。故得证。
所以a^(p - 1) × ∏(i = 1)^(p - 1) Ai ≡ ∏(i = 1)^(p - 1) Ai (mod p) 。证毕。
例：p = 5, A = {1, 2, 3, 4}, a = 2。
则aA = {2, 4, 6, 8}, aA%p = {2, 4, 1, 3}, A%p = {1, 2, 3, 4}

例题

给两个数a, p，p是质数，求a模p的乘法逆元

由费马小定理
a^(p - 1) ≡ 1 (mod p)，得 a × a^(p - 2) ≡ 1 (mod p)，
所以a^(p - 2) 就是a模p的乘法逆元。
用快速幂求即可。

#include<bits/stdc++.h>
using namespace std;
int a, p;
int quickpow(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res = res * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int main() {
	cin >> a >> p;
	if (a % p) {
		printf("%d\n", quickpow(a, p - 2, p));
	}
	return 0;
}