[BZOJ4804]欧拉心算：线性筛+莫比乌斯反演

分析

关于这道题套路到不能再套路了没什么好说的，其实发这篇博客的目的只是为了贴一个线性筛的模板。

代码

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int MAXN=10000005;

int n,cnt,prm[MAXN>>2];

LL f[MAXN];int low[MAXN];

bool vis[MAXN];

void init(int n){

	f[1]=1;

	rin(i,2,n){

		if(!vis[i]){

			prm[++cnt]=i;

			f[i]=i-2;

			low[i]=i;

		}

		rin(j,1,cnt){

			if(i*prm[j]>n) break;

			vis[i*prm[j]]=true;

			if(i%prm[j]==0){

				if(i==low[i]){

					if(i==prm[j]) f[i*prm[j]]=1ll*prm[j]*prm[j]-2*prm[j]+1;

					else f[i*prm[j]]=f[i]*prm[j];

				}

				else{

					f[i*prm[j]]=f[i/low[i]]*f[low[i]*prm[j]];

				}

				low[i*prm[j]]=low[i]*prm[j];

				break;

			}

			f[i*prm[j]]=f[i]*f[prm[j]];

			low[i*prm[j]]=prm[j];

		}

	}

	rin(i,1,n) f[i]+=f[i-1];

}

int main(){

	int T=read();

	init(10000000);

	while(T--){

		int n=read();LL ans=0;

		for(int i=1,nxti=0;i<=n;i=nxti){

			nxti=n/(n/i)+1;

			ans+=1ll*(n/i)*(n/i)*(f[nxti-1]-f[i-1]);

		}

		printf("%lld\n",ans);

	}

	return 0;

}