威尔逊定理

一、定理概述

威尔逊定理（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 <= x; i++) {
        res = res * i % P;
    }
    return res;
}

//逆元模板
long long inv(long long x) {
    return qpow(x, P-2);
}

//计算组合数
long long C(long long n, long long m) {
    if(m > 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比较大，我们还需要对模数做一些特殊处理，将计算结果乘上一个指数。