题解 | 怎么发题解啊？

一

是数学，但不是数学。

我们用数学结论保证了正确性，但用很多好玩的东西保证了前 $4$ 题不需要知道结论全能暴力 AC 。

第五题和第六题分别选用了课上被讲烂的结论和暴力题。

第七题和第八题采用了不常见的结论和不常见的所谓“根号的优雅暴力”增加区分度。

二

为什么这套题很怪。因为出题人几乎半退役了（实际上现实的做法就是退役了，但精神上嘴硬没有退役）很抱歉出不了风格全面的题目。

你是职业选手吗？

我觉得我是。

alt

A gcd

预期大家通过观察 AC 。

答案是 $a \textbf{＋} b$ 。

浅述证明思路： 在 $a, b$ 非 $0$ 时， $gcd(a, b)$ 的答案是他们的最大公约数。在 $a, b$ 存在 $0$ ， $gcd(a, b) = max(a, b)$ 。

可以有很多方法证明，当 $a, b$ 都非 $0$ 时不会是最优解。

B 整除

预期大家通过暴力 AC 。

暴力正确性：

\begin{cases} (n \textbf{＋} x) \mid (m \textbf{＋} x) \\ (n \textbf{＋} x) \mid (n \textbf{＋} x)\\ \end{cases} \Rightarrow (n \textbf{＋} x) \mid (m - n)

$m \geq 2n \Leftrightarrow \exists x$ 。

$x \in [0, m - 2n]$ 。

C 字符串

没什么新意，很快可以观察出鸽巢原理。

预期大家通过观察 AC 。

敢于暴力枚举也依旧会是对的。

正确性：

字符串长度超过 $\sum_{i = 1}^{9} i^{2} \textbf{＝} \frac{9(9 1)(9 \times 2 1)}{6} \textbf{＝} 285$ 后一定存在 $x$ 出现超过 $x$ 次。

枚举左端点，再往右枚举右端点，不会超过 $285$ 次。

D 输出答案

预期大家通过打表 AC

不难打表发现结果只有三种

d + 1 = 4
d + 1 是其他合数
d + 1 是质数

答案很明显的可以通过打表猜出。

正确性证明：

d + 1 是合数
1. 当 d + 1 = 4。
  
  显然 $3! \equiv 2 (\bmod 4)$ 。
2. 当 d + 1 是 $> 4$ 的完全平方数
  
  设 $d \textbf{＋} 1 \textbf{＝} x^{2}$ ，通过一些入门的高等数学分析显然有 $2 < x < 2x < x^{2}$ 则 $d! \textbf{＝} d \times (d - 1) \times (d - 2) \times \cdots \times 2x \times \cdots \times x \times \cdots \times 2 \times 1$ 。于是 $\exists q, q (d \textbf{＋} 1) \textbf{＝} d!$ ，即 $d! \bmod (d \textbf{＋} 1) \textbf{＝} 0$ 。
3. 当 d + 1 是非完全平方数
  
  设 $d \textbf{＋} 1 \textbf{＝} ab,\ a < b$ ，则 $d! \textbf{＝} d \times (d - 1) \times (d - 2) \times \cdots \times b \times \cdots \times a \times \cdots \times 2 \times 1$ 。于是 $\exists q, q \times (d \textbf{＋} 1) \textbf{＝} (\bmod d \textbf{＋} 1)$ ，即 $d \bmod (d 1) \textbf{＝} 0$ 。
d + 1 是质数
1. 若 $d \textbf{＋} 1 \textbf{＝} 2$ 。显然常数次枚举一下即有解。
2. 若 $d \textbf{＋} 1$ 是奇质数。由 $gcd(d, d \textbf{＋} 1) \textbf{＝} 1$ 则一定存在 $d$ 的逆元 $d^{-1}$ 满足 $d \times d^{-1} \equiv 1$ 。
考虑逆元是自己的情况： $x^{2} \equiv 1 (\bmod d \textbf{＋} 1) \Rightarrow (x - 1)(x \textbf{＋} 1) \equiv 0 (\bmod d \textbf{＋} 1) \Rightarrow x_1 \textbf{＝} 1, x_2 \textbf{＝} d$ 。

大家喜欢默认互质的模意义下，存在逆元。且基本都会证存在性（实际上只证存在性，结果并不一定是逆元）

定理：逆元唯一

这意味着 $[2, d - 1]$ 的逆元不是自己。

于是 $[2, d - 1]$ 可以被分为 $\frac{d - 2}{2}$ 组，每组的乘积为 $1$ 。这意味着 $(d - 1)! \equiv 1 (\bmod d \textbf{＋} 1)$ 。两边乘以 $d$ 得到 $d! \equiv d (\bmod d \textbf{＋} 1)$ 。

问题来了，怎么证实互质的模意义下逆元的存在性和唯一性？

存在性： 极其好证明，Euler 定理或者同余方程搞搞就有了，大家都会。这里证略。

唯一性：

设 $P \textbf{＝} \{x_1 < x_2 < x_3 < \cdots < x_{\varphi(m)} \}$ 是 $\leq m$ 的 $\varphi(m)$ 个与 $m$ 互质的数。

则只需证 $Q \textbf{＝} \{ x_1^{\varphi(m) - 1}, x_2^{\varphi(m) - 1}, x_3^{\varphi(m) - 1}, \cdots, x_{\varphi(m)}^{\varphi(m) - 1} \}$ 在 $\bmod m$ 意义下是 $P$ 的一个排列。

只需要观察两点：
- $gcd(x_i^{\varphi(m) - 1} \bmod m, m) \textbf{＝} 1$ 。证明： 考虑反证。 $gcd(x_i, m) \textbf{＝} 1$ 时 $gcd(x_i^{\varphi(m) - 1}, m) \neq 1 \Leftrightarrow m \mid \varphi(m) - 1$ ，显然与 $\varphi(m) < m$ 矛盾。 $\square$
- $\forall i \neq j, x_i^{\varphi(m) - 1} \not \equiv x_j^{\varphi(m) - 1}$ 。证明： 考虑反证。若存在 $x_i^{\varphi(m) - 1} \equiv x_j^{\varphi(m) - 1} (\bmod m)$ ，则 $x_j \cdot x_i^{\varphi(m)} \equiv x_i \cdot x_j^{\varphi(m)} (\bmod m)$ ，由 Euler 定理则 $x_i \equiv x_j (\bmod m)$ ，显然与 $1 \leq x_i \neq x_j < m$ 矛盾。
这两点足以证明 $Q$ 在 $\bmod m$ 意义下是 $P$ 的一个排列。

$\square$

为什么你不去打表呢？出题人懂这个结论，但你觉得这个结论是你赛场上当场能推出来的吗？（本校 push ，外校爸爸忽略这句）

E 背景

很常见的结论。

gcd(a_{1}, a_{2}, a_{3}, \cdots, a_{n}) \mid d \Leftrightarrow a_{1} x_{1} \textbf{＋} a_{2} x_{2} \textbf{＋} a_{3} x_{3} \textbf{＋} \cdots \textbf{＋} a_{n} x_{n} \textbf{＝} d

证明：

离散课老师似乎已经把证明讲烂了。

$\not \square$

F 位反转

没什么新意的暴力，可暴力可 DP 。

DP 很短很好写。

考虑一个二的幂次 $n$ 。

考虑一个数 $x$ 右移一位得到 $x>>1$ 。实际上相当于 $R(x)$ 左移一位得到 $R(x>>1)$ 。

于是 $R(x>>1)$ 右移一位得到 $R(x\ and\ ((1 << n - 1) - 1))$ 。最高位补上 $x$ 的最低位： $x\ and\ 1$ 即可。

于是

dp_{R(x)} \textbf{＝} (dp_{R(x >> 1)} >> 1)\ or\ e(x\ and\ 1) \times (1 << n - 1)

很精悍。

G sqrt

不常见的结论。

双指针套 st 表查一下最小的 $d > m$ 。

只需暴力往后找到一个 $p$ 。

由质数定理 $p$ 可以在 $O(\ln d)$ 次枚举找到。质数判断的优化算法随意，理论上 $O \left (\sqrt{\frac{d}{\ln d}} \right )$ 的算法就足够了。

数据应该是 $a_i \leq 2^{31} - 1$ 忘记描述且错误描述所以锅卡了 inf = 0x3f3f3f3f ……抱歉，实际数据里没有放找不到 d 的情况。

然后是：

$p \textbf{＝} 2$ 有解。

证明： 若 $p \textbf{＝} 2$ ，常数次枚举一下就有解。 $\square$
$p$ 为奇质数。 $m^{\frac{p - 1}{2}} \equiv 1 (\bmod p)$ 和 $\exists x$ 是充要的。 $m^{\frac{p - 1}{2}} \equiv -1 (\bmod p)$ 和 $\not \exists x$ 是充要的。

证明：

充分性：

若 $p$ 是奇质数，一定存在原根 $g$ 满足 $g \bmod p$ 的阶 $\delta_p(g) \textbf{＝} \varphi(p)$ 。

于是任取某个原根为 $g$ ，会有 $g^{0}, g^{1}, g^{2}, \cdots, g^{\varphi(p) - 1}$ 是 $\bmod p$ 的一个既约剩余系。又 $\varphi(p) \textbf{＝} p - 1$ ，于是 $g^{0}, g^{1}, g^{2}, \cdots, g^{p - 1}$ 是 $\bmod p$ 的一个完全剩余系，于是 $\exists k \in [0, \varphi(m) - 1], m \equiv g^{k}$ 。

若 $m^{\frac{p - 1}{2}} \equiv 1 (\bmod p)$ ，简单变形 $m^{\frac{p - 1}{2}} \equiv g^{k \frac{p - 1}{2}} \equiv 1 \equiv g^{(p - 1) \times \frac{k}{2}} \Rightarrow 2 \mid k$ 。

于是 $x$ 可以开根， $x \equiv g^{\frac{k}{2}} \equiv g^{\frac{k}{2} (p - 1)} \equiv 1$ 即是一个解。

若 $m^{\frac{p - 1}{2}} \equiv -1 (\bmod p)$ ， $2 \mid k \Rightarrow g^{(p - 1) \frac{k}{2}} \equiv 1$ ，显然与 $g^{(p - 1)\frac{k}{2}} \equiv -1$ 矛盾，于是 $x$ 不能开根。

必要性：

若 $\exists x$ 有 $x^{2} \equiv m (\bmod p)$ ，由 $p$ 是奇质数则有 $x^{2 \frac{p - 1}{2}} \equiv m^{\frac{p - 1}{2}} \equiv x^{p - 1} \equiv 1 \not \equiv -1$ 。

$\square$

$p$ 为奇质数。 $m^{\frac{p - 1}{2}}$ 有且仅有两个解 $\pm 1$ 。

证明： 由 $gcd(m, p) = 1$ 根据 Euler 定理有 $m^{p - 1} \equiv 1 \equiv m^{2 \frac{p - 1}{2}}$ 。显然 $m^{\frac{p - 1}{2}} \equiv \pm 1$ 。 $\square$