自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 22:51:44，当前版本为作者最后更新于2025-01-04 23:50:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

推柿子。但是卡了好久谔谔。

---

我们设 $f(x)=x!\oplus p$。

展开

$$f(x)=(1\times 2\times \dots \times (x-1)\times x)\oplus p $$

把 $p$ 的倍数提出来并且进行一个变形

$$f(x)=\{[(0\times p+1)\times \dots \times (1\times p-1)]\times[(1\times p+1)\times\dots\times(2\times p-1)]\times\dots\times[(\lfloor\frac{x-p}{p}\rfloor\times p+1)\times\dots\times(\lfloor\frac{x}{p}\rfloor\times p-1)]\times[(\lfloor\frac{x}{p}\rfloor\times p+1)\times \dots \times x]\times(\lfloor \frac{x}{p} \rfloor!\times p) \}\oplus p $$

化简

$$f(x)=\{[1\times 2 \times \dots \times (p-1)]^{\lfloor \frac{x}{p} \rfloor}\times (1\times 2 \times \dots \times (x\bmod p))\times(\lfloor \frac{x}{p} \rfloor!\oplus p)\}\oplus p $$

再化简

$$f(x)=\{[(p-1)!]^{\lfloor \frac{x}{p} \rfloor}\times (x\bmod p)!\times f(\lfloor \frac{x}{p} \rfloor)\}\bmod p $$

根据威尔逊定理化简得

$$f(x)=[(p-1)^{\lfloor \frac{x}{p} \rfloor}\times (x\bmod p)! \times f(\lfloor \frac{x}{p} \rfloor)]\bmod p $$

我们可以快速幂求出 $(p-1)^{\lfloor \frac{x}{p} \rfloor}$，预处理 $(x\bmod p)!$，然后递归计算结果。

做完了。

核心代码：

int f(int x){
    if(x<p)return sum[x];
    int ans=qpow(p-1,x/p,p);
    return ans*sum[x%p]%p*f(x/p)%p;
}