威尔逊定理QWQ

考虑作者太懒了，博客里面的同余符号都用等号代替 qwq # 威尔逊定理 威尔逊定理大概是这么个东西： $$(p-1)!=-1(mod ~~ p)$$ 其中 p 当然是质数辣~ # Proof 然后我们考虑证明？ 首先： $$p-1=-1(mod ~~ p)$$ 那么我们只需要证明 $(p-2)!=1 (mod~~ p)$ 就好了... 也就是说，除去 1 后，如果 $2,3,...,p-2$ 能够两两配对，且每对数乘积 模 p 后为 1 的话，威尔逊定理就成立了，然后我们考虑这其实就是对于 $2,3,...,p-2$ 去找 模 p 意义下的逆元啊... 然后考虑一下二次剩余里面的衍生芝士我们可以知道对于 $x^2=1$ 只有两个解（1，p-1），而这两个数已经被我们安排掉了，也就是说 $2,3,...,p-2$ 中**不存在某个数的逆元是自己本身**... 然后我们还知道逆元有**唯一性**与**互反性**，于是乎这些数自然是一一对应的辣~ 证毕！ # Application 这个...显然可以用在阶乘求解上？ 但是用途不广...可能可以用来优化快速阶乘？ XD 我们考虑这个式子已经成立了： $$(p-1)!=-1(mod ~~ p)$$ 那么我们现在要求的是： $$n!~(mod ~~ p)$$ 然后我们考虑威尔逊定理能怎么用进去... （现在我们不考虑 $n=p-1$ 或 $p-2$ 的极端情况，$n=p-1$ 时答案为 $p-1$ ，$n=p-2$ 时 答案为 $1$ ，可特判） 首先： $$n! ·\Big( (n+1)(n+2)...(p-1)\Big) =-1(mod~~ p)$$ 我们令 $p-n =x$ ： $$n! ·\Big( (p-x+1)(p-x+2)...(p-1)\Big) =p-1(mod~~ p)$$ 那么： $$\begin{aligned}( n!)'=&(p-x+1)(p-x+2)...(p-2)\\=&(-1)^{x-2}(x-1)(x-2)...(2)\\=&(-1)^x (x-1)!\\=& (-1)^{p-n}(p-1-n)! \\=& (-1)^{n+1}(p-1-n)! \end{aligned}$$ 上面 $p-x+1$ 变到 $x-1$ 其实就是把负号提出来了... 然后我们发现只要求出 $(p-1-n)!$ 然后乘上 $(-1)^n$ 这样的优化...可能没什么用？但是也是优化就是了...