威爾遜定理

一、定理概述

威爾遜定理（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比較大，我們還需要對模數做一些特殊處理，將計算結果乘上一個指數。