令 $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 imes 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 imes mu(frac{k}{i})$
然后后面那个 $sum_{i|k} i imes 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 ",ans); } int main() { // setIO("input"); int T; init(); scanf("%d",&T); while(T--) solve(); return 0; }