威尔逊定理：若p为素数，则p可以整除(p-1)!+1。
用同余方程表示为：(p-1)! ≡ -1 (mod p)
证明如下
充分性：
当p=1时，(p-1)! ≡ 0 (mod p)
当p=4时，(p-1)! ≡ 2 (mod p)
当p>4时，当p为完全平方数时，设k²=p，探讨2k和p的大小，因为k²-2k在k>2的时候永远大于0，所以p>2k>k，所以(p-1)! ≡ 1*2*......*k*......*2k*......*(p-1) ≡ 0 (mod p)
当p不为完全平方数时，设p=a*b，因为p>a>b，所以(p-1)! ≡ 1*2*......*a*......*b*......*(p-1) ≡ 0 (mod p)。
必要性：
当p=2时，(p-1)! ≡ -1 (mod p)
当p>2时，因为p为质数，则根据费马小定理存在a有pow(a,p-2)，只要a与pow(a,p-2)不同余，则pow(a,p-2)为a的逆元。
假设二者同余，则有a²与pow(a,p-1)同余于1，解出来a=1或者p-1（x² ≡ 1(mod p)的解只有1和p-1，所以假设不成立，得证。
威尔逊定理的应用：
若存在n>p，要求计算 n! 中除了能被p整除的其他所有正整数相乘在模 p 的环境下，可以利用分块计算，每块为p的长度，前p-1项为(p-1)!,最后一项系数为出现第i个(p-1)!的意思，大概这样：
所以最后只要计算利用威尔逊定理，再计算(n/p)! 和最后的尾巴部分就好了。时间复杂度为o(p+logp n)。
代码如下：
int factmod(int n, int p) {
vector<int> f(p);
f[0] = 1;
for (int i = 1; i < p; i++) f[i] = f[i - 1] * i % p;
int res = 1;
while (n > 1) {
if ((n / p) % 2) res = p - res;
res = res * f[n % p] % p;
n /= p;
}
return res;
}
标签：int,res,定理,威尔逊,pow,......,mod From： https://www.cnblogs.com/DLSQS-lkjh/p/17627163.html