以 下 的 p 表 示 素 数 以下的p表示素数 以下的p表示素数
1. x 为 质 数 φ ( x ) = x − 1 1.x为质数 \varphi(x)=x-1 1.x为质数φ(x)=x−1
2. x 与 p 互 质 时 2.x与p互质时 2.x与p互质时
φ ( x ⋅ p ) = φ ( x ) ⋅ p \varphi(x\cdot p)=\varphi(x)\cdot p φ(x⋅p)=φ(x)⋅p
φ ( x ⋅ p 2 ) = φ ( x ) ⋅ φ ( p 2 ) = φ ( x ) ⋅ p ⋅ ( p − 1 ) = φ ( x ⋅ p ) ⋅ ( p − 1 ) \varphi(x\cdot p^2)=\varphi(x)\cdot \varphi(p^2)=\varphi(x)\cdot p\cdot(p-1)=\varphi(x\cdot p)\cdot(p-1) φ(x⋅p2)=φ(x)⋅φ(p2)=φ(x)⋅p⋅(p−1)=φ(x⋅p)⋅(p−1)
题目
题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000002;
int fl[N],prime[N],phi[N],n,i,j,tot,T;
ll ans[N],tmp[N];
int main(){
	tmp[1]=1;//注意是tmp，不是phi
	for (i=2;i<N;i++){
		if (!fl[i]) prime[++tot]=i,phi[i]=i-1;
		for (j=1;i*prime[j]<N;j++){
			fl[i*prime[j]]=1;
			if (i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
		tmp[i]=(ll)phi[i]*i>>1;
	}
	for (i=1;i<N;i++)
		for (j=i;j<N;j+=i) ans[j]+=tmp[i];
	scanf("%d",&T);
	while (T--) scanf("%d",&n),printf("%lld\n",ans[n]*n);
}