2025 CCH非专业级软件能力认证提高级第五轮总结

类人群星闪耀时：

T4纯暴力拿88的

T3假贪心拿68的

又找规律写出数学题的

卡评测的

骂出题人的

打错考号的

T1：U576864，T2：U576869，T3：U576872，T4没找到。

预期：看运气 + 72 + 看运气 + 20

实际：44 + 72 + 48 + 60

由于四道题都没过，所以这次换个形式。

开始读题，边读便稍微想想，T2还稍微推了推。

不知道为什么读了1h，耗时间的有点多了，但是4题都看了一下。

看完题之后认为T2好写一点，于是开始想T2。

把式子用前缀和拆开，题目就变成了求 $\sum\limits_{i=1}^{n} \varphi^{(\max_{j=1}^{i}\varphi(j)-B)} (i)$。

因为 $\varphi(x) < x$，于是可以发现，当 $\max_{j=1}^{i}\varphi(j)-B \ge 100$ 左右时，$\varphi^{(\max_{j=1}^{i}\varphi(j)-B)} (i) = 1$。

所以我们只要暴力求几百个的样子。

但是当我想到这里时，忘记了 $B$ 是固定的，$T$ 又比较大，所以我一直在想，还没有想到正解，气炸了。

想了T2很久了，都过去2h了还没有一份代码，于是我赶紧回头打T1。

先直接暴力跑两边最短路，但是调了45min了还没调出来。

已经只剩1h15min了，还一分都没拿到，心态有点崩了。

于是我只能退一步，打个暴搜遗憾离场，还剩1h。

开打T2暴力，72pts很好拿，直接写个线性筛，求下欧拉函数就可以了。

但是……线性筛怎么写来着？

然后我就开始回忆线性筛，大概10min终于想起来了。

但是我还是不会求欧拉函数啊。

然后又回忆，回忆5min不想想了，就找规律。

最后发现，当 $i \bmod prime_j > 0$ 时，$\varphi(i \times prime_j) = \varphi(i) \times \varphi(prime_j)$，否则 $\varphi(i \times prime_j) = i \times \varphi(prime_j)$。

赶紧打完，还剩30min。

T3想到了个贪心，但是是错的，大样例都没过。

刚好看到有随机数据，抱着赌一赌的心态，就直接走了，成功赌到48pts。

T4直接暴力，纯纯暴力，刚好打完。

1h15min极限救场终于拿到224pts，纯心态王。

T2为什么想了那么久？纯读题不仔细或者说健忘，距离正解就一步之遥。

T1怎么暴力都打错了？其实不是最短路的问题。我当时为了判断字符串是否相等，写了一堆重载啥的，把自己写乱了，最后直接爆炸了（最终暴搜的代码也是不正确的，44pts不止TLE，也WA了不少）

还有一些远古学的忘记了，只能说没有复习。