题解：P14304 【MX-J27-T1】分块

· · 题解

我们观察数据范围发现若 n 为完全平方数，则答案为 \sqrt{n} \times 3 - 2。

我们容易发现对于任意相邻两个完全平方数所组成的区间 x^2\sim (x+1)^2 - 1 中合法的数字仅仅只有三个，那么 1\sim n 这个区间就有 (\sqrt{n}-1)\times3 + 1 个，化简可得上述式子。

若 n 不是完全平方数，那么可以找到离 n 最近且 < n 的完全平方数，我们令离 n 最近且 < n 的完全平方数为 m，这样就可以分为两个区间，一个是 1\sim m-1，另一个是 m \sim n，第一个区间和第二个区间都容易求出，那么公式即为 \lfloor \sqrt{n} \rfloor\times 3-3+\lfloor \frac{n-m+1}{\lfloor \sqrt{n} \rfloor} \rfloor。

代码需注意根号精度问题。

十年 OI 一场空，不开 long long 见祖宗。