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