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

· · 题解

方法一：暴力

枚举 x，时间复杂度 \Theta(qn)，30 分。

方法二：打表

预处理枚举 x 从 1 到 10^6 ，时间复杂度 \Theta(q+\alpha)，\alpha 是数组 n 的值域，40 分。

方法三：找规律

我们来看当 n = 30 时 x 的取值：
1 2 3 4 6 8 9 12 15 16 20 24 25 30
我们注意到每一个大于 1 完全平方数前面都有 2 个不是完全平方数的数。我们可以求出小于等于 n 的完全平方数个数就是 \lfloor{ \sqrt{n}\rfloor}。

当 n 是完全平方数时

答案就是 3(\sqrt n - 1) + 1 = 3\sqrt n - 2，因为每个大于 1 的完全平方数都带了 2 个其他数，共计 3 个。

当 n 不是完全平方数时

我们考虑比 \lfloor \sqrt n \rfloor ^ 2 大的合法的 x，我们将最开始的打表结果（当 n = 30 时 x 的取值）差分得到：
1 1 1 1 2 2 1 3 3 1 4 4 1 5
我们发现，对于一个完全平方数 x，它下一个符合题目条件的数就是 x + \sqrt x，再下一个就是 x + 2\sqrt x，更后面的又是完全平方数了。我只需要看 n - \lfloor \sqrt n \rfloor ^ 2 里有多少个 \lfloor \sqrt n \rfloor 即可，最终答案是

3\lfloor\sqrt n\rfloor - 2 + \left\lfloor\dfrac{n - \lfloor \sqrt n \rfloor ^ 2}{\lfloor \sqrt n \rfloor}\right\rfloor

。实际上，这个式子在当 n 是完全平方数时同样适用。

Code

#include <iostream>
#include <cmath>
using namespace std;
int q;
long long n,s;
void sqr(){//用来修正sqrt()本身的误差，时间复杂度极小。
    s = sqrt(n);
    while (s * s > n) --s;
    while ((s + 1) * (s + 1) <= n) ++s;
}
int main(){
//  freopen("sqrt.in","r",stdin);
//  freopen("sqrt.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> q;
    while (q--){
        cin >> n;
        sqr();
        cout << 3 * s - 2 + (n - s * s) / s << '\n';
    }
}

UPD