题目描述

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。

题目分析

求

#include <cstdio>  
#include <cstring>   
#include <algorithm>  
using namespace std;   
long long n,ans;  
long long f[10010];  
void init(long long x)  
{  
    long long i;  
    for(i=1;i*i<x;i++)  
        if(x%i==0)  
            f[++f[0]]=i,f[++f[0]]=x/i;  
    if(i*i==x) f[++f[0]]=i;  
}  
long long phi(long long x)  
{  
    long long sum=x;  
    for(long long i=2;i*i<=x;i++)  
        if(x%i==0)  
        {  
            sum/=i,sum*=i-1;  
            while(x%i==0) x/=i;  
        }  
    if(x!=1)  sum/=x,sum*=(x-1);  
    return sum;  
}  
int main()  
{  
    scanf("%lld",&n);  
    init(n);  
    for(int i=1;i<=f[0];i++) 
        ans+=phi(n/f[i])*f[i];  
    printf("%lld",ans);  
}