CF1957E 做题小计 ： 威尔逊定理

被数论虐爆了(悲)

威尔逊定理

• \(\forall p\in prime , (p-1)! \equiv -1 (\bmod p)\)

为什么啊？
对于 \(2\) 很显然。
对于 \(p\) ，我们知道 \(inv(p-1)=p-1=-1\)，然后 \(inv(1)=1\)
然后因为 \(p\in prime\) ，所以对于任意 \(a\in[2,p-2]\) ，都有 \(inv(a)\) 与它唯一对应。因为 \(inv(inv(a))=a\) 。
所以 \(\prod\limits_{i=1}^{p-2}=1\) 所以就证完了。

正题

这道题要我们推式子。

\(C(i,j)=\frac{\prod_{k=i-j+1}^i}{j} \space \bmod j\)
然后我们知道整除的是 \(j\times\lfloor \frac i j\rfloor)\) 所以就变成
\(C(i,j)=(j-1)!\times \lfloor \frac i j\rfloor \bmod j\)

然后因为合数只有 \(4\) 是特殊的，除了 \(4\) 所有合数的因子都能不重复的在 \(1\to x\) 表示出来。

所以如果 \(a\) 是合数，有 \((a-1)!=0\)

如果 \(a\) 是质数， \((a-1)! =-1\)

然后对于每个质数，把它的贡献筛出来插分一下就行了。

然后就没了。时间复杂度 \(O(n\ln n)\) 。