费马小定理是数论中的一个重要定理，在编程竞赛中常用于求乘法逆元。以下是详细解释：
一、定理内容
如果 p 是一个质数，且 a 不是 p 的倍数（即 a 和 p 互质），那么：
a^(p-1) ≡ 1 (mod p)
换句话说：a 的 p-1 次方除以 p 的余数等于 1。
二、推导乘法逆元
在模运算中，我们经常需要计算 a 除以 b 的余数（即 a × (1/b) mod p）。但模运算中不能直接做除法，需要用到乘法逆元。
乘法逆元的定义：
如果 b × x ≡ 1 (mod p)，那么 x 就是 b 在模 p 下的乘法逆元，记作 b^(-1)。
三、费马小定理求逆元
由费马小定理：b^(p-1) ≡ 1 (mod p)
变形：b × b^(p-2) ≡ 1 (mod p)
对比逆元定义：b × x ≡ 1 (mod p)
可得：x = b^(p-2) mod p
结论：b 的乘法逆元就是 b^(p-2) % p（要求 p 是质数，且 b 不被 p 整除）。
四、代码实现（快速幂）
求逆元需要计算 b^(p-2)，指数很大（例如 p=998244353 时，p-2≈10^9），需要用快速幂优化：
五、具体例子
假设模数 p = 998244353，求 5 的逆元：
5^(-1) = 5^998244351 mod 998244353
计算结果为 598946613（实际值）。
验证：5 × 598946613 = 2994733065，2994733065 mod 998244353 = 1 ✓
六、在排列组合题中的应用
在排列组合题中，我们需要计算：
组合数 C(N, K) = N! / (K! × (N-K)!) mod p
步骤：
预处理所有阶乘 fact[i] = i! % p
用费马小定理求 fact[N] 的逆元 invFact[N]
倒推出所有阶乘的逆元
C(N, K) = fact[N] × invFact[K] × invFact[N-K] % p
这样就把除法取模转化为了乘法取模，避免了直接除法的困难。
七、注意事项
模数必须是质数：费马小定理只适用于 p 为质数的情况。
a 不能是 p 的倍数：如果 a % p = 0，逆元不存在。
本题中模数 998244353 是质数，且题目数据保证 K! 和 (N-K)! 都不是 p 的倍数（因为 N ≤ 10^6 < p），所以可以安全使用费马小定理求逆元。
总结：费马小定理提供了一个在模质数意义下将除法转化为乘法的方法，是组合数学取模问题的核心工具。
