Description

 给出一个数字N

Input

第一行为一个正整数T，表示数据组数。

接下来T行为询问，每行包含一个正整数N。

T<=5000,N<=10^7

题解： 求 $\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(gcd(i,j))$

 

$=\sum_{d=1}^{n}\varphi(d)\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==d]$

 

$=\sum_{d=1}^{n}\varphi(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j)==1]$

 

其中 $\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==1]=2\times\sum_{i=1}^{n}\varphi(i)-1$

 

可以用数形结合来思考：

 

$\sum_{i=1}^{n}\sum_{j=1}^{i}[gcd(i,j)==1]=\sum_{i=1}^{n}\varphi(i)$

 

这个式子可以看作是对角线一半的欧拉函数值(以 $i$ 为横坐标，$j$ 为纵坐标）

 

而 $\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==1]$ 正好是对角线折叠过去的结果.

 

不过还要减去 $(1,1)$ 多出来的贡献（只有 $1$ 是和自己本身互质的数）

 

令 $Sum(n)=\sum_{i=1}^{n}\varphi(i)$

 

答案为 $\sum_{d=1}^{n}\varphi(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j)==1]$

 

$\Rightarrow\sum_{d=1}^{n}\varphi(d)\times(2\times\sum_{i=1}^{\frac{n}{d}}\varphi(i)-1)$

 

$\Rightarrow\sum_{d=1}^{n}\varphi(d)\times(2\times Sum(\frac{n}{d})-1)$

 

$\Rightarrow2\times\sum_{d=1}^{n}\varphi(d)Sum(\frac{n}{d})-Sum(n)$

 

提前与处理一下欧拉函数前缀和即可.

#include
     
      #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; }