自动搬运

查看原文

来自洛谷，原作者为

	zzx0102 原 sto_5k_orz || AFO on 2023.10.21

搬运于2025-08-24 22:43:24，当前版本为作者最后更新于2023-07-03 14:43:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不喜欢打原神，但是很喜欢这道题。

介绍一下这题的非正解。

首先根据题意，可以暴力枚举所有平方数，然后暴力标记倍数。

这样的时间复杂度是 $O(n+T)$ 的，可以获得 $30$ 分。

#include<bits/stdc++.h>
using namespace std;
const int N = 10000010; bool vis[N]; int s[N];
void init(int n) {
	for(int i = 2; i * i <= n; i++) {
		int k = i * i;
		for(int j = k; j <= n; j += k) vis[j] =  1;
	}
	for(int i= 1; i <= n; i++) s[i] = s[i - 1] + vis[i];
}
signed main() {
	init(1e7); int t; cin >> t;
	while(t--) {
		int n; cin >> n;
		cout << s[n] << '\n';
	}
	return 0;
}

还不够。

考虑到正解和答案有一定内在联系，于是计算三个样例的输入与输出的比值。

答案是：

将第一组数据排除，我们发现答案与输入的比值大约是 $0.392$，同时此题允许 $20000$ 的误差，那么这样大概率是可以的，但是 $30$ 分。

于是暴力打表，打出前 $10^7$ 组数据答案与输入的比值的平均值。

#include<bits/stdc++.h>
using namespace std;
const int N = 10000010; bool vis[N]; int s[N];
void init(int n) {
	for(int i = 2; i * i <= n; i++) {
		int k = i * i;
		for(int j = k; j <= n; j += k) vis[j] =  1;
	}
	for(int i= 1; i <= n; i++) s[i] = s[i - 1] + vis[i];
}
signed main() {
	init(1e7);
	long long sum = 0, c = 0;
	for(int i = 1; i <= 10000000; i++) sum += s[i], c += i;
	cout << 1.0 * sum / c;
	return 0;
}

得出的比值 $v$ 为 $0.392073$。

依然 $50$ 分，但是十分接近正解了。

考虑到前 $10000$ 组数据误差较大，同时再增加 $10^7$ 个样本容量，使得答案更加精确，然后多打几位小数，发现答案约为 $0.392072898146$。

不过只有 $70$ 分。

然后经过反复调整比值 $v$，得出 $v=0.39207289814597$ 时，可以通过本题。

与我用计算器算出来的题解里面讲的估计的比值 $1-\dfrac{6}{\pi^2}=0.39207289814597337133672322074163$ 是十分接近的，至少精确到了 $14$ 位，而本题的正解是整除分块，只是复杂度太高，不可以通过，需要估测。

有些时候推不出正解的比值，可以考虑通过打表等手段求出类似的值。

于是我们用红题的码量+橙题难度的打表薄纱了一道蓝题。