A

算法 1

手算

期望通过 Subtask 1，得分 20 分。

算法 2

设 $n = R$

写程序在 $[L,R]$ 暴力枚举并检验。检验的复杂度为 $O(n^2)$，“看起来”总复杂度为 $O(n^3)$。

事实上，后面我们会看到，这种算法的期望复杂度为 $O(n^2 \log n)$

期望通过 Subtask 1 ~ 2，得分 40 分。

算法 3

注意到

$$a \frac{(x+1)!}{x} \equiv -a \pmod {x}$$

等价于

$$a(x+1)(x-1)! + a \equiv 0 \pmod {x} \; \; \; (1)$$

其成立的一个充分但不必要条件为（实际上，算法 4 告诉我们，这是一个充要条件）：

$$(x+1)(x-1)! + 1 \equiv 0 \pmod {x} \; \; \; (2)$$

$$x(x-1)! + (x-1)! + 1 \equiv 0 \pmod x$$

$$(x-1)! + 1 \equiv 0 \pmod x$$

因此我们不再需要枚举 $a$，直接枚举 $x$ 然后进行检验即可。时间复杂度 $O(n)$。

期望通过 Subtask 1 ~ 3，得分 70 分。

算法 4

注意到，$[0, x^2]$ 在 $x > 1$ 内总包含素数，因此对任意 $x$ 必存在 $a_0 \in [0, x^2]$，使得 $a_0 \bot x$。

即，在模 $x$ 的意义下，存在一个 $a_0$ 有逆元。将其乘在 $(1)$ 上必得到 $(2)$，因此 $(2)$ 是 $(1)$ 的一个充要条件。

因此，我们只需要构造一个 $x$ 满足 $(x-1)! \equiv -1 \pmod x$。

随后，我们似乎对这个突然冒出来的同余式不知所措。因为下一步我们没有任何思路。

不过，观察两边，我们发现左边（即$(t-1)!$那一部分），一定包含了$1,2,3,\cdots, t-1$的所有因子，但它是否包含$t$的因子呢？如果包含，那么左边的式子一定为$0$，就不可能与$t-1$模$t$同余了。（因为显然$t \bot (t-1)$）.那么，$(t-1)!$的约数包含$t$吗？不知道。所以，这暗示我们，这个$t$与素数有关。

猜想1.1： 如果 $(t-1)! \equiv -1 \equiv t-1 \pmod t$，则$t$必为素数

猜想1.2： 如果$t$为素数，则$(t-1)! \equiv -1 \equiv t-1 \pmod t$。

我们先来解决猜想1.1。

证明： 设$\exists t_0\notin \mathbb P$且$(t_0-1)\equiv -1 \pmod t$。
则必$\exists 1< a\leqslant b < t_0$，使得$t_0=ab$。不妨先假设$a\ne b$
首先，$a,b\ne t_0-1$。
若不然则有$b(t_0-1)=t_0$或$a(t_0-1)=t_0$或$(t_0-1)^2=t_0$ ，这显然均与$t_0$的定义不符。
注意到$(t-1)! = 1\times 2\times \cdots \times a \times \cdots \times b \times \cdots \times (t-1)$
故有$a \mid (t_0-1)!$。又因为
$$(t_0-1)!\equiv -1 \pmod t$$ 故显然$t_0 \mid \left((t_0-1)! + 1\right)$。 故$a \mid \left((t_0-1)! + 1\right)$。 所以$a \mid \left((t_0-1)!+1-(t_0-1)!\right)=1$ 即$a=1$，与$a>1$矛盾。 同理可得$a=b$时的矛盾。 故$\nexists a,b, \mathrm{s.t.}(t_0-1)\equiv -1 \pmod t$有$t_0=ab$。

因此，我们顺利证明了猜想1.1。

定理1.1： 如果 $(t-1)! \equiv -1 \equiv t-1 \pmod t$，则$t$必为素数。

下面我们证明猜想1.2。

证明： 当$t=2$时，原式显然成立。
下面，我们设$t>2$。

注意到$t$为素数，因此$\forall 1\leqslant x\leqslant p-1$，都$\exists x^{-1}$使得 $$xx^{-1}\equiv 1 \pmod t$$ 令$x=x^{-1}$，即 $$x^2\equiv 1 \pmod t$$ 则显然只有$x=1$或$x=t-1$。

不妨设$2\leqslant y \leqslant t-2$，则显然$2\leqslant y^{-1}\leqslant t-2$，且$y\ne y^{-1}$。
由于${\left(y^{-1}\right)}^{-1}=y$，因此可知，在此范围内，可将$2 \sim t-2$分为$\dfrac{t-3}{2}$对，使得每对的乘积在模$t$的意义下为$1$。
即 $$2\times 3\times \cdots \times (t-3)\times (t-2) \equiv 1 \pmod t$$ 即 $$(t-2)! \equiv 1 \pmod t$$ 故 $$(t-1)!\equiv (t-2)!(t-1)\equiv(t-1)\equiv -1\pmod t$$

因此我们顺利证明了猜想1.2。

定理1.2： 如果$t$为素数，则$(t-1)! \equiv -1 \equiv t-1 \pmod t$。

将定理1.1与定理1.2结合，即得

定理1.3（Wilson 定理）： $(t-1)!\equiv -1\pmod t\Longleftrightarrow t \in \mathbb P$。

因此，由定理 1.3，我们只需要在 $[L,R]$ 构造一个素数。显然，其可以在 $O(\sqrt n \log n)$ 的时间复杂度内完成。

时间复杂度：$O(\sqrt n \log n)$，期望得分 100 分。

B

算法 1

爆搜。

时间复杂度 $O\left(\sum^T_{i=1} i!\right) = O(n!)$，期望通过 Subtask 1，得分 10 分。

算法 2

显然这就是个普及组难度的dp……

设 $f_n$ 表示 $n$ 所对应的答案，显然：

$$f_n = n! - \sum^{n-1}_{k=1} k! f_{n-k}$$

暴力计算即可，时间复杂度 $O(n^2 + T)$，期望通过 Subtask 1 ~ 2，得分 50 分

算法 3

注意到这个式子是个卷积，我们采用分治NTT优化，时间复杂度 $O(n \log^2 n + T)$，得分 100 分。

C

咕咕咕