NOIP2024模拟赛27 | 选手只有 T4 AC

又是高一 rk7。这场大众分太高了。我以为有很多人过 T4 的。

80(95)+80+45(55)+100，sy 机子太慢了。

T1：

场上只想出来 \(A^{1/4}\log^2A\) 的单次做法，只有 80。即枚举小的那个底数。

结论：满足条件的数可以表示成 \(a^2b^3\)。

？？？

这样直接枚举 \(\min (a,b)\le 4000\) 的质因子就做完了啊。

考虑证明。先排除一个质因子次数是 1 的情况，一定不行。设 \(x=\prod a_i^{p_i}(p_i\ge 2)\)。

注意到所有 \(p_i\ge 2\) 都可以拆分成若干个 2 和 3 的和。所以就做完了。

T2：

优秀的爆搜可以获得 80 分。我以为正解不是指数复杂度……

数据范围在指数以上，但仅仅略大于指数时，可以考虑推导题目性质，减小指数大小。如将 \(O(2^n)\) 通过性质优化到 \(O(2^{n/k})\)。

不要轻易相信大样例。过了极限不要激动。不会轻易得满分。还是多想一下有没有优化的余地。