（题目传送门)
这道题重点就在于“他允许你的答案与真正的答案有着不超过 \(2\times 10^4\) 的绝对误差”，从此可以引申出两种方法。
法一
由于误差较大，我们可以直接算概率。
我们考虑问题的反面，即有多少个数不是完全平方数的倍数。
对于一个质数 \(p\)，一个数是 \(p^2\) 倍数的概率是 \(\dfrac{1}{p^2}\)，那不是 \(p^2\) 倍数的概率就是 \(1-\dfrac{1}{p^2}\)。
由乘法原理得不是完全平方数的概率为 \(\prod\limits_p{(1-p^{-2})}\)。
这时我们需要用到欧拉乘积公式：
\[\sum\limits_n{n^{-s}}=\prod\limits_p{(1-p^{-s})^{-1}} \]待入得
\[\prod\limits_p{(1-p^{-2})}=\dfrac{1}{\sum\limits_n{n^{-2}}} \]右边分母是所有正整数的平方倒数和，等于 \(\dfrac{\pi^2}{6}\)，所以左边等于 \(\dfrac{6}{\pi^2}\)。
因此一个数是完全平方数的倍数的概率即为 \(1-\dfrac{6}{\pi^2}\)，最终答案为 \(n(1-\dfrac{6}{\pi ^2})\).
法二
不难发现问题即求 \(n-\sum\limits_{i=1}^n{\mu^2(i)}\)。
而我们知道 \(\sum\limits_{i=1}^n\mu^2(i)=\sum\limits_{i=1}^{\sqrt{n}}\mu(i)\left\lfloor\dfrac{n}{i^2}\right\rfloor\)，于是我们直接估算，左 \(\approx \sum\limits_{i=1}^n\dfrac{\mu(i)}{i}\left\lfloor\dfrac{n}{i}\right\rfloor=\sum\limits_{i=1}^n(\dfrac{\mu}{id}*1)(i)\)，而又因为 \((\dfrac{\mu}{id}*1)(n)=\sum\limits_{d\mid n}{\dfrac{\mu(d)}{d}}=\dfrac{\sum\limits_{d\mid n}{\mu(d)\times \dfrac{n}{d}}}{n}=\dfrac{\varphi(n)}{n}\)，所以原式即 \(\sum\limits_{i=1}^n\dfrac{\varphi(i)}{i}\)。
而 \(\dfrac{\sum\limits_{i=1}^n\dfrac{\varphi(i)}{i}}{n}\) 表示随机选取正整数对 \((x,y)\) 使得 \(1\leq x\leq y\leq n\) 且 \((x,y)\) 互质的概率，欧拉级数告诉我们它在 \(n\rightarrow +\infty\) 时约等于 \(\dfrac{6}{\pi ^2}\)，因此答案约为 \(n(1-\dfrac{6}{\pi ^2})\)
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const double pi=acos(-1.0);
LL n;
void mian()
{
scanf("%lld",&n);
double tmp=1.00-6.00/pi/pi;
cout<<(LL)(1LL*n*tmp)<<endl;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
mian();
return 0;
}