思路：首先给出几个结论：
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).
代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<set> 7 #include<vector> 8 #define ll __int64 9 #define M 50005 10 #define inf 1e10 11 #define mod 1000000007 12 using namespace std; 13 int prime[M],cnt; 14 bool f[M]; 15 void init() 16 { 17 cnt=0; 18 memset(f,0,sizeof(f)); 19 for(int i=2;i<M;i++){ 20 if(!f[i]) prime[cnt++]=i; 21 for(int j=0;j<cnt&&i*prime[j]<M;j++){ 22 f[i*prime[j]]=1; 23 if(i%prime[j]==0) break; 24 } 25 } 26 } 27 ll pows(ll a,ll b) 28 { 29 ll ans=1; 30 while(b){ 31 if(b&1) ans*=a; 32 b>>=1; 33 a*=a; 34 } 35 return ans; 36 } 37 ll dfs(ll n) 38 { 39 ll ans=1,j; 40 for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++){ 41 if(n%prime[i]==0){ 42 j=1; 43 n/=prime[i]; 44 while(n%prime[i]==0){ 45 j++; 46 n/=prime[i]; 47 } 48 ans*=(ll)(prime[i]*j-j+prime[i])*pows(prime[i],j-1); 49 } 50 } 51 if(n>1) ans*=(ll)(2*n-1); 52 return ans; 53 } 54 int main() 55 { 56 ll n; 57 init(); 58 while(scanf("%I64d",&n)!=EOF){ 59 printf("%I64d ",dfs(n)); 60 } 61 return 0; 62 }