题解：P15794 【MX-J28-T1】「Cfz Round 8」Sqrt Problem

· · 题解

10 分做法

当 n \le 2 且 k \le 10^5 时，可以直接模拟。

若 n=1，则 1 开方后仍是 1，每次开方得 1 分，因此 k 分需要 k 次操作。

若 n=2，则 2 不是完全平方数，需要先加 2 变成 4，然后开方得 2，进入循环。每获得 1 分需要 2 次操作（一次加 2，一次开方）。因此 k 分需要 2k 次操作。

直接模拟即可，复杂度 O(k)，可以通过测试点 1,2,3。

40 分做法

当 k=1 时，问题退化为：从 n 出发，只进行一次开方，最少需要多少次操作。

设 r = \lceil \sqrt{n} \rceil。由于只能加 2，不能改变奇偶性，因此若 r 与 n 奇偶性不同，则 r 需要加 1（因为 (r+1)^2 - n 与 (r+2)^2 - n 奇偶性相同，且 (r+1)^2 更大，但为了奇偶匹配，(r+1)^2 是可行的，且比 (r+2)^2 更优）。那么需要加 2 的次数为 \frac{r^2 - n}{2}，再加上一次开方，总操作数为 \frac{r^2 - n}{2} + 1。

直接计算即可，复杂度 O(\log n)，可以通过测试点 5,6。

60 分做法

当 n \le 10^5 且 k \le 10^5 时，可以完全模拟 k 次操作过程。

每次操作：

找到最小的 m 满足 m^2 \ge cur 且 m \equiv cur \pmod{2}。

累加加 2 次数 \frac{m^2 - cur}{2}。

将 cur 更新为 m，累加一次开方操作。

重复 k 次即可。由于 n 较小，cur 会在几次操作后迅速减小，但最坏情况下 k 次操作仍需 O(k \log n) 时间，可以通过测试点 7。

80 分做法

当 n \le 10^9 且 k \le 10^9 时，k 太大无法模拟。

观察发现，所有正整数在操作下最终都会进入三个不动点：1,2,3。这是因为：

当 x 较大时，找到的 m 一定小于 x，因此 x 单调递减。

只有当 x 很小时，才可能出现 m = x 的情况。通过不等式 (x-2)^2 < x 解得 x \le 3 时，可能存在更小的同奇偶数平方不小于 x 的情况，因此 1,2,3 是仅有的不动点。

具体地：

$2$：需要加 $2$ 到 $4$，再开方得 $2$，每分需要 $2$ 次操作。 $3$：需要加 $2$ 到 $9$，再开方得 $3$，每分需要 $4$ 次操作。 因此，我们可以先模拟前若干步直到 $cur \le 3$，然后根据剩余分数 $r$ 直接计算后续操作数： 若 $cur = 1$，加 $r

若 cur = 2，加 2r

若 cur = 3，加 4r

由于每次 cur 至少开方，模拟步数不超过 O(\log \log n)，可以通过测试点 8,9。

正解

当 n,k \le 10^{18} 时，上述方法已经足够，只需要注意实现细节：

计算 \lceil \sqrt{n} \rceil 时，可以用二分或整数平方根函数，注意精度。

处理 cur 进入不动点后的批量计算，所有中间运算均在 long long 范围内，无需使用 __int128 或特判。

对于 n 较大但 k 较小的情况，直接模拟即可；对于 k 很大的情况，利用不动点优化。

时间复杂度 O(\log \log n \cdot \log n)，空间复杂度 O(1)，完结撒花！