【鲜花】唔噗噗噗

雕像爆炸的充要条件是“唔噗噗噗”。

这时候我们就称 “雕像爆炸” 可以推出 “唔噗噗噗”，同时 “唔噗噗噗” 也可以推出 “雕像爆炸”。这记作：

$$\text{“雕像爆炸”}\Leftrightarrow\text{“唔噗噗噗”}$$

和符号 $\Leftrightarrow$ 被迫在一起的两个可怜的小东西有什么共同特征呢？我们一起来看看吧。

从左到右

给定一个周长为 $L$ 的圆，从一个点出发，有 $n$ 个黑白熊雕像，编号为 $1$ 到 $n$，第 $i$ 个雕像在顺
时针 $X_i$ 米处，如果你没有在 $T_i$ 秒内收集到这个黑白熊雕像，那么这个雕像就会发出“唔噗噗噗”
的声音然后爆炸。

想读懂这句话是什么意思，关键在于要读懂这句话。

首先我们来看第一句，“给定一个周长为 $L$ 的圆。”很酷啊！我们大家都知道圆周长公式为

$$L=2\pi r$$

同时，我们可以在下面的一句话中找到一些特殊而奇妙、神奇又美好、可爱又萌萌的性质：

第一行两个整数 $n,L$ 代表雕像数和圆的周长。

太对了！这说明 $L$ 是一个地地道道的整数，也就是说 $L\in\mathbf{Z}$。其实我们还可以发现这里的 $L$ 显然是一个正整数。太对了！一个更紧确的界就是显而易见的：$L\in\mathbf{N}^+$。

同时，我们还注意到 $\pi$ 是一个著名的无理数，所以我们可以惊奇地发现：$r$ 不是一个有理数！

这句话的另一个表达方式是：$r\in \mathbf{R}\setminus\mathbf Q$。

还有一个表达方式：$r$ 不能被表达为两个互质整数 $p,q$ 的比值。

$\Huge\text{太对了！}$

中间那些部分没啥用，我们就先跳过了。

---

广告之后马上回来！

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

你好，我是广告。

---

我们接着品析上面的这段话。

大家看，“你好”这个词象征着欢迎，而广告这个词则是表达了——

对不起看错行了

关键的部分来了！

如果你没有在 $T_i$ 秒内收集到这个黑白熊雕像，那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。

啊，我们看到我们想要的东西了。

“唔噗噗噗”是一个地地道道的拟声词，它的发音为：

$$\text{wu}\!\sim\sim\quad \text{pupupu}\!\sim\sim$$

“黑白熊”也是一个关键，需要理解。想到黑白熊，我们立刻想起来一个非常有名以至于妇孺皆知的动物：熊猫。这就不难发现为什么要建造“黑白熊雕像”了！敬仰熊猫，为它立雕像，这不是人间大义、值得歌颂千古的伟大善事！来，我们肃立一分钟，为我们可爱的大熊猫敬礼！

诶，那雕像为什么会爆炸呢？

毁坏文物雕像，会遭到判刑；毁坏大熊猫雕像，却是不尊重国家的行为。再结合一个我们忽略的重要信息：

现在 JOI 君在这个点……

JOI，即日本国赛。

小日子的阴谋浮上了水面！

结合“唔噗噗噗”这个非常难崩又难以理解的词语，不难想到小日子们想用这样可爱的外表来进行一系列阴谋活动。这正是他们能干出来的事！

---

这样我们就得到了结论：可爱的黑白熊猫雕像爆炸是一场早有预谋的攻击，其主谋为小日子国度，妄图使用最新研发的代号 $\text{ID-wppp}$ 炸弹炸毁这些雕像。

这样我们证明了一件事：“唔噗噗噗”是可以推出雕像爆炸的，即

$$\text{“唔噗噗噗”}\Rightarrow\text{“雕像爆炸”}$$

从右到左

雕像爆炸怎么能推出“唔噗噗噗”呢？

我们利用反证法。

首先我们证明一个引理：计算等差数列的和的算法太快了，不够慢。

大家知道计算等差数列的和的公式吗？我们记项数为 $n$，首项与末项分别为 $a_1,a_n$，那么其和为

$$S=\dfrac{n(a_1+a_n)}{2}$$

为了看出我们是怎么劣化这个算法的，不妨设 $a_i=i$。

我们来推一个式子：

$$\begin{aligned}\sum_{i=1}^ni&=\sum_{i=1}^n\sum_{d|i}\varphi(d)\\&=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}1\\&=\sum_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor\varphi(i)\end{aligned}$$

我们可以预处理出 $\varphi(n)$，利用数论分块即可达到 $O(n)$ 预处理、$O(\sqrt n)$ 计算的复杂度。

能不能再慢点呢？可以！

我们预处理出 $1\sim O(n^{\frac23})$ 内的 $\varphi$ 函数值，然后使用杜教筛来计算出 $\varphi$ 函数的前缀值、进而求出它的区间和。

这样的时间复杂度是什么呢？一个 naive 的上界显然是 $O(n^\frac76)$ 的，但是这并不紧却，我们来看看究竟是什么。

我们可以认为，整个计算过程分为 $3$ 部分：

1. $1\sim\sqrt{n}$，此时数论分块的块长为 $1$，每次调用杜教筛的时间复杂度为 $O(1)$（预处理值域内），这一部分的时间复杂度为 $O(\sqrt n)$。
2. $\sqrt n\sim n^\frac23$，此时数论分块的块长不再是 $1$，但是杜教筛的时间复杂度仍然是 $O(1)$，杜教筛调用的次数是 $O(\sqrt n-\sqrt[3]n)$ 的，因此这部分的时间复杂度是 $O(\sqrt n)$。
3. $n^\frac23\sim n$，这部分杜教筛的耗时不再是 $O(1)$ 而是 $O(n^\frac23)$，而块数为 $O(\sqrt[3]n)$，因此此时间复杂度为 $O(n)$。

综上，我们得到了这个算法的时间复杂度是线性时间查询、$O(n^\frac23)$ 时间预处理。

---

回过头来，我们证明这个引理有什么用呢？

我们仔细审视“唔噗噗噗”一词。第一个字“唔”可以被看做一个等差数列的首项，而后面的“噗”象征着对每一项增加 $1$。总而言之，“唔噗噗噗”可以被看做数列

$$a=\{1,2,3,\cdots,n\}$$

我们捡雕像，可以看做对这个数列求和，而经过上面的讨论，我们需要的时间是 $O(n)$ 的，十分巨大，以至于会让雕像爆炸。雕像爆炸起源于唔噗噗噗，也结束于唔噗噗噗。

这样我们证明了一件事：“雕像爆炸”是可以推出唔噗噗噗的，即

$$\text{“雕像爆炸”}\Rightarrow\text{“唔噗噗噗”}$$

---

我们回顾一下我们的探索过程。

证明部分生动具体地应用了“若 $A\subseteq B$，而 $B\subseteq A$，则 $A=B$”的证明思路。这为我们带来了一个警示：任何命题都有其背后的故事，任何命题也都有其背后的逻辑。

在证明过程中，我们还介绍了一种由 @秦屎皇 口胡的 $O(n^\frac23)$ 预处理、$O(n)$ 解决等差数列求和问题的算法，利用了数论算法中的“欧拉函数 $\varphi(n)$”以及“杜教筛”等高级算法，以劣化原有的算法。

好了，今天的分享就到这里，我是 @秦屎皇。