为什么要求逆元
当我计算((a % p) (+/-/* ) (b % p)) % p的时候都可以直接这样使用，但是当我们处理除法的时候，比如((a%p)/(b%p))%p，这个方法就失效了，但在大数运算时，直接除法可能产生精度问题或溢出。
什么是费马小定理
1.当a是p的倍数：
a^p≡a(mod p)
2.当a与p互质，即gcd(a, p) = 1:
a^p−1≡1(mod p)
如何用费马小定理求逆元
逆元的定义
在模 p 运算中，如果存在整数 x 使得 b × x ≡ 1 (mod p)，则称 x 为 b 的模 p 逆元，记作 b⁻¹。
除法转乘法的原理
在模运算中，我们定义除法为：a/b ≡ a × b⁻¹ (mod p)。
因此，(a/b) % p = (a × b⁻¹) % p。
费马小定理求逆元
当 p 是质数且 b 与 p 互质时，由费马小定理：
b^(p-1) ≡ 1 (mod p)
将上式两边同时乘以 b⁻¹：
b^(p-1) × b⁻¹ ≡ 1 × b⁻¹ (mod p)
b^(p-2) ≡ b⁻¹ (mod p)
因此，逆元 x = b^(p-2) % p。
完整计算过程
要求 (a/b) % p：
- 验证 p 是质数且 gcd(b, p) = 1
- 计算逆元
x = b^(p-2) % p（使用快速幂） - 结果 =
(a × x) % p
例子
求4 % 5 的逆元
x = 4^(5-2) = 4^3 = 64 % 5 = 4
验证： (4*4)%5 = 1, 正确