P8883

Miyamizu_Mitsuha · 2023-09-11 23:23:00 · 题解

写在前面：这是一篇几乎没有任何数论基础的人也能看的懂的题解，因为作者就没有数论基础。

很有趣的一道题，感觉思维难度并没有蓝，看到可以有误差 + 庞大的数据范围，于是一眼看比值。

容易想到，对于每个数，能被 p^2 整除的概率是 \frac{1}{p^2}，也就是 p^{-2}，因为每 p^2 才会出一个能整除的数。现在我们想求的是至少有一个数能整除完全平方数的概率，那么可以先算出来一个数不能整除完全平方数的概率，也就是 1-p^{-2}，然后乘法原理算出所有数都不能整除完全平方数的概率，即为 \prod_{p} \left(1 - p^{-2}\right)。最后再用 1 减一下就好了。

然后感觉这个东西很熟悉，于是把欧拉乘积公式翻了出来：

我们把欧拉乘积公式的 s 替换成 2，得

然后两边取倒数，得

发现右边就是我们想要求的东西。

左边的分母是所有正整数的平方倒数和，等于 \frac{\pi^2}{6}，这里不细说了。所以，不含平方因子数的概率为：

由于我们算的是所有数都不能整除完全平方数的概率，所以至少有一个能整除的概率就是

最后，将这个概率乘以 n，就可以得到在 1 到 n 范围内存在平方因子数的数的期望数量：

代码：

#include <bits/stdc++.h>
using namespace std;
const long double p=acos(-1.0);
int main(){
    long long t,n;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<(long long)(n*(1.0-6.0/p/p))<<endl;
    }
    return 0;
}

再说几句闲话，这题题面有点坑，我一开始理解成了恰好有一个能整除的，所以推出来了个这个式子，不知道对不对，有没有大佬能帮忙看看，可能也许大概收敛于 \frac{3}{8}（猜的）。