

本编的学习要求:知道是什么,怎么用即可。
费马小定理:
【同余式】
- 对于两个整数 a、b,模相同的模数 m,得到的余数相同,则称 a、b 模 m 同余,记作:
。 - a 和 b 模上 m 的余数相同,叫同余。
性质:
- 同加性:两个整数加上相同的数,不影响结果,
。 - 同减性:如果同加性的 c 为负数,那么就出现了同减性,两个整数减去相同的数,也不影响结果。
- 同乘性:两个整数乘上相同的数,不影响结果,
。
📌这也是为什么之前的题目遇到 "乘加减" 运算时,可以处处取模的原因。
📌除法不能处处取模,本编就是通过 逆元,将除法转化乘 乘法,从而做到处处取模。
【费马小定理】
- 如果 p 为质数,且 a、p 互质,则 a^(p – 1) % p = 1,官方记作:

- 例如:p = 5,a = 2:2^(5 – 1) % 5 = 2^4 % 5 = 16 % 5 = 1,官方记作:

【乘法逆元】
- 若 a 和 m 互质,且满足同余方程,则有
,即 ax % m = 1,式子中 x 就是 a % m 的乘法逆元,记作:
。 - 例如:
。
应用:
即上文在同余式的红字:"📌除法不能处处取模,本编就是通过 逆元,将除法转化乘 乘法,从而做到处处取模。"
- 现求 (b ÷ a)% p,等价于 (b *
)% p,
是 a % p 的乘法逆元,这个乘法逆元求解方法一:费马小定理 + 快速幂。 - 费马小定理的作用:"a^(p – 1) % p = 1" 等价于 "a * a^(p – 2) % p = 1",对比 "ax % m = 1" 可知:乘法逆元
等于 "a^(p – 2)"。 - 快速幂的作用:计算 "a^(p – 2)"。
- 乘法逆元求解方法一的使用条件是:p 为质数,a 与 p 互质;p 作为模数,题目一般给的都是质数,且很大,a 比 取模的模数 p 小,a 与 p 互质,所以条件一般符合。
#include <iostream>
using namespace std;
typedef long long LL;
// 必须要保证 a,p 互质,且 p 为质数。
LL qpow(LL a, LL b, LL p)
{
LL ret = 1;
while(b)
{
if(b & 1) ret = ret * a % p;
b >>= 1;
a = a * a % p;
}
return ret;
}int main()
{
LL x, p; cin >> n >> p;
cout << qpow(x, p – 2, p) << endl;
return 0;
}
时间复杂度: - 与快速幂一致,为O(log n)。




![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
