思路：首先给出几个结论：
1.gcd(a,b)是积性函数；
2.积性函数的和仍然是积性函数；
3.phi(a^b)=a^b-a^(b-1);
记 f(n)=∑gcd(i,n),n=p1^e1*p2^e2……;
则 f(n)=∑d*phi(n/d) (d是n的约数)
=∑(pi*ei+pi-ei)*pi^(ei-1).
代码如下：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#define ll __int64
#define M 50005
#define inf 1e10
#define mod 1000000007
using namespace std;
int prime[M],cnt;
bool f[M];
void init()
{
cnt=;
memset(f,,sizeof(f));
for(int i=;i<M;i++){
if(!f[i]) prime[cnt++]=i;
for(int j=;j<cnt&&i*prime[j]<M;j++){
f[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
}
ll pows(ll a,ll b)
{
ll ans=;
while(b){
if(b&) ans*=a;
b>>=;
a*=a;
}
return ans;
}
ll dfs(ll n)
{
ll ans=,j;
for(int i=;i<cnt&&prime[i]*prime[i]<=n;i++){
if(n%prime[i]==){
j=;
n/=prime[i];
while(n%prime[i]==){
j++;
n/=prime[i];
}
ans*=(ll)(prime[i]*j-j+prime[i])*pows(prime[i],j-);
}
}
if(n>) ans*=(ll)(*n-);
return ans;
}
int main()
{
ll n;
init();
while(scanf("%I64d",&n)!=EOF){
printf("%I64d\n",dfs(n));
}
return ;
}