本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
令 $x=\prod p_{i}^{a_{i}}$
则 $f(x)=\prod p_{i}^{\frac{a_{i}}{2}}$
也就是说 $f(x)$ 等于最大的 $y$ 满足 $y^2|f(x)$
$\sum_{i=1}^{n} f(i)$ 可化为 $\sum_{i=1}^{ \sqrt{n}} i \times g(\frac{n}{i^2})$
其中 $g(x)$ 表示 $1$ ~ $x$ 中有多少个无平方因子数.
$g(x)$ 有一个很经典的莫比乌斯函数容斥：$g(x)=\sum_{i=1}^{\sqrt x} \mu(i)\frac{x}{i^2}$
原式等于 $\sum_{i=1}^{\sqrt n} \sum_{j=1}^{\sqrt{\frac{n}{i^2}}} \mu(j) \frac{n}{i^2j^2}$
令 $k=ij$，$\Rightarrow \sum_{k=1}^{n} \frac{n}{k^2} \sum_{i|k} i \times \mu(\frac{k}{i})$
然后后面那个 $\sum_{i|k} i \times \mu(\frac{k}{i})=\phi(k)$.
所以最后答案等于 $\sum_{k=1}^{n} \frac{n}{k^2} \phi(k)$
code:
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 4000003
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int cnt;
int vis[N],prime[N],phi[N];
void init() {
phi[1]=1;
for(int i=2;i<N;++i) {
if(!vis[i]) {
prime[++cnt]=i,phi[i]=i-1;
}
for(int j=1;j<=cnt&&prime[j]*i<N;++j) {
vis[i*prime[j]]=1;
if(i%prime[j]) {
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
else {
phi[i*prime[j]]=phi[i]*prime[j];
}
}
}
}
void solve() {
ll n,ans=0;
scanf("%lld",&n);
ll s=sqrt(n);
for(ll i=1;i<=s;++i) {
ans+=(n/(i*i))*1ll*phi[(int)i];
}
printf("%lld\n",ans);
}
int main() {
// setIO("input");
int T;
init();
scanf("%d",&T);
while(T--) solve();
return 0;
}
