答案就是 ∑ d * phi(n / d) (d | n) 。。没得说。。

1 #include
      
        2 #define clr(a,x) memset(a,x,sizeof(a)) 3 #define rep(i,l,r) for(int i=l;i
       
        1) ans=ans/x*(x-1);32     return ans;33 }34 int main()35 {    36     ll n=read(),ans=0;37     int m=int(sqrt(n));38     rep(i,1,m+1){39         if(n%i==0){40             ans+=i*phi(n/i);41             if(i*i<=n) ans+=(n/i)*phi(i);42         }43     }44     printf("%lld\n",ans);45     return 0;46 }
       
      

还有orzlsj的方法：

注意到h(n) = ∑ d * phi(n / d) (d | n) 是狄利克雷卷积的形式, 而且f(x) = x 和 f(x) = phi(x) 都是积性函数, 所以答案h(x) 也是积性函数.

所以h(x) = Π h(p^k) (p 是 x 的质因数) 

由phi(p^k) = p^k - p^(k-1), h(p^k) 很好求. 化简一下得到 h(p^k) = (k + 1) * p^k - k * p^(k - 1) 

1 #include
      
        2 #define clr(a,x) memset(a,x,sizeof(a)) 3 #define rep(i,l,r) for(int i=l;i
       
        1) ans=ans/x*(x-1);32     return ans;33 }34 int main()35 {    36     ll n=read(),ans=1;37     int m=int(sqrt(n));38     rep(i,2,m+1){39         if(n%i==0){40             int k=0;41             while(n%i==0){42                 k++;n/=i;43             }44             ans*=(k+1)*pow(i,k)-k*pow(i,k-1);45         }46     }47     if(n!=1) ans*=2*n-1;48     printf("%lld\n",ans);49     return 0;50 }
       
      

2705: [SDOI2012]Longge的问题

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 1514  Solved: 943

[][][]

Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数，为N。

Output

一个整数，为所求的答案。

Sample Input

6

Sample Output

15

HINT

 

【数据范围】

对于60%的数据，0<N<=2^16。

对于100%的数据，0<N<=2^32。

 

 

Source

[ ][ ][ ]