此博客停更

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3944

本来想留着给初三爷出题。。然而都没几个会欧拉函数的，所以就写个题解等我忘了看……

最开始给我灵感的是codevs月赛的一道题，它的一个子问题是求

$\sum_{i=1}^{n}\sigma \left ( i \right )$,其中$\sigma \left ( n \right )= \sum_{d|n}d$

介个东西怎么做呢，当然并不能直接做喽，当时比利直接秒出%%%，he said :"This is a foolish thing." 他是考虑每个数对答案的贡献，我还是暴力推了推公式

$\sum_{i=1}^{n} \sigma \left ( i \right )= \sum_{i=1}^{n}\sum_{j=1}^{n}[j|i]\cdot j= \sum_{i=1}^{n}i\cdot [\frac{n}{i}]$

-->http://www.lydsy.com/JudgeOnline/problem.php?id=2226

跟比利做题时不时就会出现这种我还没做过的题$0.0$

$O(T\sqrt n)$

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000010
#define ll long long
int i,j,k,m,n,x,y,T,phi[N],o;ll ans;
int main(){
	phi[1]=1;
	for(i=2;i<=N;++i)if(!phi[i])for(j=i;j<=N;j+=i){
		if(!phi[j])phi[j]=j;
		phi[j]=phi[j]/i*(i-1);
	}
	for(ans=0,T=read();T--;){
		for(ans=0,n=read(),o=sqrt(n),i=1;i<=o;++i)if(n%i==0){
			if(i!=1)ans+=1ll*i*phi[i]/2;
			else ans+=1;
			if(i*i!=n)ans+=1ll*n/i*phi[n/i]/2;
		}
		printf("%lld\n",1ll*ans*n);
	}
}