一、定理概述
威尔逊定理（Wilson’s Theorem）是一个关于质数的性质，通常是指以下这个定理：
若p为质数，则(p-1)！ ≡ -1 (mod p)
即p是质数时，(p-1)的阶乘模p等于-1。
由此可以得到一个直接判断质数的方法，若一个数n能够满足(n-1)! ≡ -1 (mod n)，则n是质数。
二、证明过程
威尔逊定理的证明过程比较简单，这里简单介绍一下：
设p为一个大于2的质数，则p-1是一个偶数，可以将(p-1)!写成两个部分的积：
(p-1)! = 1*2*3*...*(p/2)*(p/2+1)*...*(p-1)
其中(p/2+1)~(p-1)组成的这部分可以表示为：
(p/2+1)*(p/2+2)*...*(p-1) = (-1)*(-2)*...*(-p/2) = (-1)^(p/2)*[(p/2)!]^2
将上式带入主式，得到：
(p-1)! = [(p-1)/2]!^2 * (-1)^(p/2) * (mod p)
当且仅当(p-1)/2为偶数时，(-1)^(p/2)等于1。因此：
(p-1)! ≡ [(p-1)/2]!^2 (mod p)
又因为p是质数，所以剩下的部分[(p-1)/2]!^2肯定不是0，而是模p意义下的一个非零平方数。因此，当(p-1)!模p等于-1时，[(p-1)/2]!^2模p等于1，从而[(p-1)/2]! ≡ 1或(p-1) (mod p)。
若[(p-1)/2]! ≡ (p-1) (mod p)，则(p-1)/2 + 1 ~ p-1这部分中肯定有一个数可以与[(p-1)/2]!相乘等于-1，即形如n(p-n) ≡ -1 (mod p)。显然这个n就是(p-1)/2。
由此可以得到，当(p-1)!模p等于-1时，p必然是质数。
三、应用与代码示例
威尔逊定理不仅可以用于判断质数，还可以用于计算排列组合等问题。以下是一个使用威尔逊定理计算组合数的代码示例：
int P = 998244353;
//快速幂模板
long long qpow(long long a, long long b) {
long long res = 1 % P;
while(b) {
if(b & 1) res = res * a % P;
a = a * a % P;
b >>= 1;
}
return res;
}
//阶乘模板
long long fac(long long x) {
long long res = 1;
for(int i = 2; i n) return 0;
long long res = fac(n) * inv(fac(m)) % P * inv(fac(n-m)) % P;
if(n >= P) res = res * qpow(P, n/P) % P;
return res * fac(n%P) % P * inv(fac(m) * fac(n-m)%P) % P;
}
这个代码中，我们先定义模数为998244353（一个大质数），然后使用快速幂模板、阶乘模板和逆元模板计算阶乘和逆元。最后计算组合数时，如果n比较大，我们还需要对模数做一些特殊处理，将计算结果乘上一个指数。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/241364.html
微信扫一扫 
支付宝扫一扫 