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

· · 题解

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

思路

看到如此之大的数据范围，首先想到的应该是：打表。
结果：

1
2
3
4
6
8
9
12
15
16
20

发现了什么！！！所有完全平方数都在这之中（虽然这应该是废话）。
我们可以尝试分组：（其中，每一列为 1 组）

1  4   9  16
2  6  12  20
3  8  15 ...

所以，我们得出，可以每 3 个数为一组。每一组第一个数是一个完全平方数，然后依次加上这个完全平方数的算术平方根。
或者，如果用数学符号表示，则是这样的：

x^2, x^2 + x, x^2+2x

根据这样的规律，就可以轻轻松松的写出代码了。

代码（PAC）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int q;
    cin >> q;
    while (q --){
        unsigned long long n; cin >> n;
        unsigned long long t = sqrt(n);
        unsigned long long f = t * t;
        unsigned long long ans = (t - 1) * 3;
        ans ++;
        while (f + t <= n){
            ans ++; f += t;
        }
        cout << ans << endl;
    }
    return 0;
}

提交记录：https://www.luogu.com.cn/record/242880354
那为什么会WA了呢？
如果仔细测试了下发数据点的话，你就会发现最后一个点也WA了。
输入：

999999999999999999

应输出：

2999999997

实际输出：

2999999998

这时候调试一下，比如尝试输出 f。
输出：

1000000000000000000

怎么回事？为什么会比原数大呢？
sqrt函数的精度问题！

代码（AC）

那怎么处理这个问题呢？
人工操作！
就是在发现结果不对时，手动调小一点。
（赛后我询问了Deepseek，确认了在大部分情况下这样做是可行的）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int q;
    cin >> q;
    while (q --){
        unsigned long long n; cin >> n;
        unsigned long long t = sqrt(n);
        unsigned long long f = t * t;
        if (f > n){
            t --; f = t * t;
        }
        unsigned long long ans = (t - 1) * 3;
        ans ++;
        while (f + t <= n){
            ans ++; f += t;
        }
        cout << ans << endl;
    }
    return 0;
}

通过记录：https://www.luogu.com.cn/record/242882936