专栏文章

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

MMinions_love_dameile
P14304题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mini9pjm
此快照首次捕获于
2025/12/02 02:51
3 个月前
此快照最后确认于
2025/12/02 02:51
3 个月前
查看原文

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

思路

看到如此之大的数据范围，首先想到的应该是：打表。
结果：
CPP
1
2
3
4
6
8
9
12
15
16
20
发现了什么！！！所有完全平方数都在这之中（虽然这应该是废话）。
我们可以尝试分组：（其中，每一列为 11 组）
CPP
1  4   9  16
2  6  12  20
3  8  15 ...
所以，我们得出，可以每 33 个数为一组。每一组第一个数是一个完全平方数，然后依次加上这个完全平方数的算术平方根。
或者，如果用数学符号表示，则是这样的：
x2,x2+x,x2+2xx^2, x^2 + x, x^2+2x 根据这样的规律，就可以轻轻松松的写出代码了。

代码（PAC）

CPP
#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了。
输入：
CPP
999999999999999999
应输出：
CPP
2999999997
实际输出：
CPP
2999999998
这时候调试一下，比如尝试输出 f。
输出：
CPP
1000000000000000000
怎么回事？为什么会比原数大呢？
sqrt函数的精度问题！

代码（AC）

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

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...