BZOJ 4804: 欧拉心算 欧拉函数

#include<bits/stdc++.h>
#define maxn 10000003 
#define M 10000000
#define ll long long 
using namespace std;
void setIO(string s)
{
	string in=s+".in"; 
	freopen(in.c_str(),"r",stdin); 
}
int cnt; 
bool vis[maxn];
int prime[maxn], phi[maxn];  
ll sumv[maxn];  
inline void Linear_shaker()
{
	phi[1]=1; 
	int i,j; 
	for(i=2;i<=M;++i)
	{
		if(!vis[i]) prime[++cnt]=i, phi[i]=i-1; 
		for(j=1;j<=cnt&&1ll*i*prime[j]<=M;++j)
		{
			vis[i*prime[j]]=1; 
			if(i%prime[j]==0) 
			{
				phi[i*prime[j]]=phi[i]*prime[j]; 
				break; 
			}
			phi[i*prime[j]]=phi[i]*(prime[j]-1); 
		}
	} 
	for(i=1;i<=M;++i) sumv[i]=sumv[i-1]+phi[i]; 
}
inline void solve()
{
	int n,i,j; 
	scanf("%d",&n); 
	ll re=0; 
	for(i=1;i<=n;i=j+1)
	{
		j=(n/(n/i)); 
		re+=(sumv[j]-sumv[i-1])*(sumv[n/i]*2-1); 
	}
	printf("%lld\n",re); 
}
int main()
{
	// setIO("input"); 
	Linear_shaker(); 
	int T; 
	scanf("%d",&T);
	while(T--) solve();
	return 0; 
}