bzoj2226: [Spoj 5971] LCMSum（欧拉函数）

$以下的p表示素数$以下的p表示素数
$1.x为质数\phi \left(x\right)=x-1$1.x为质数φ(x)=x−1
$2.x与p互质时$2.x与p互质时
$\phi (x\cdot p)=\phi \left(x\right)\cdot p$φ(x⋅p)=φ(x)⋅p
$\phi (x\cdot p^2)=\phi \left(x\right)\cdot \phi \left(p^2\right)=\phi \left(x\right)\cdot p\cdot (p-1)=\phi (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);
}