BZOJ 4804 欧拉心算

题目大意

求$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} \varphi(\gcd(i,j))$.

简单题!

$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} \varphi(\gcd(i,j)) \ =\sum\limits_{d=1}^{n} \varphi(d) \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} [\gcd(i,j)=1] \ =\sum\limits_{d=1}^{n}\varphi(d) 2\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(i)-1$

之后令$F(n) = 2\sum\limits_{i=1}^{n}\varphi(i)-1$，分块一下就搞定了。

#include <cstdio>
#include <algorithm>
using namespace std;
#define R register
#define N 10000000
int phi[N+1],prm[N+1];
long long sum[N+1],res[N+1];
bool v[N+1];
int main()
{
	R int cnt=0;
	phi[1]=res[1]=1;
	for(int i=2;i<=N;++i)
	{
		if(!v[i]) prm[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*prm[j]<=N;++j)
		{
			v[i*prm[j]]=true;
			if(i%prm[j]) phi[i*prm[j]]=phi[i]*(prm[j]-1);
			else {phi[i*prm[j]]=phi[i]*prm[j];break;}
		}
	}
	for(int i=1;i<=N;++i) sum[i]=sum[i-1]+phi[i];
	for(int i=2;i<=N;++i) res[i]=res[i-1]+(phi[i]<<1);
	R int T,n;
	R long long ans;
	scanf("%d",&T);
	while(T--)
	{
		ans=0;
		scanf("%d",&n);
		for(int d=1,l;d<=n;d=l+1) l=n/(n/d),ans+=res[n/d]*(sum[l]-sum[d-1]);
		printf("%lld\n",ans);
	}
}