2018 南京网络赛 J-Sum(积性函数)

Sum

#include<bits/stdc++.h>
using namespace std;
const int N=2e7+7;
typedef long long ll;
int prime[N],tot=0;
ll f[N]={0};
bool vis[N]={0};
void pre(){
    f[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i])prime[++tot]=i,f[i]=2;
        for(int j=1;j<=tot&&i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%(1LL*prime[j]*prime[j])==0){
                f[i*prime[j]]=0;break;
            }
            else if(i%prime[j]==0){
                f[i*prime[j]]=f[i/prime[j]];break;
            }else f[i*prime[j]]=f[i]*2;
        }
    }
    for(int i=1;i<N;i++)f[i]+=f[i-1];
}
int main(){
    pre();
    int t;cin>>t;
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%lld\n",f[n]);
    }
}