SP4168 题解

· · 题解

发现这个东西其实就是：

\sum^n_{i=1}\mu^2(i)

观察到一个数 i 可以对 \left\lfloor\frac n{i^2}\right\rfloor 个数产生影响，使其不为无平方因子数。

但是这样会算重，因为含平方因子数会继续算，所以只考虑无平方因子数的影响，发现这就是 \mu 的定义。

所以答案即为 \sum^n_{i=1}\left\lfloor\frac n{i^2}\right\rfloor\mu(i)。

因为 i\ge\sqrt n 时没贡献，所以上界其实是 \sqrt n。

时间复杂度为 O(\sqrt n+T\sqrt [4]{n})。

Code:

#include<bits/stdc++.h>
#define int long long
#define N 10000005
using namespace std;

int tot,pri[N],inp[N],mu[N];

signed main(){
    mu[1]=1;
    for(int i=2;i<=N-5;i++){
        if(!inp[i]) pri[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&pri[j]*i<=N-5;j++){
            inp[pri[j]*i]=true;
            if(!(i%pri[j])) break;
            mu[pri[j]*i]=-mu[i];
        }
        mu[i]+=mu[i-1];
    }
    int t;cin>>t;
    while(t-->0){
        int n,ans=0;
        scanf("%lld",&n);
        for(int l=1,r;l<=n;l=r+1){
            if(n/(l*l)==0) break;
            r=__builtin_sqrt(n/(n/(l*l)));
            ans+=(mu[r]-mu[l-1])*(n/(l*l));
        }
        printf("%lld\n",ans);
    }
}