P8883 幻想中成为原神 题解

· · 题解

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

介绍一下这题的非正解。

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

这样的时间复杂度是 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.3,0.392,0.392

将第一组数据排除，我们发现答案与输入的比值大约是 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 位，而本题的正解是整除分块，只是复杂度太高，不可以通过，需要估测。

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

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