Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一个整数，为N。
Output
一个整数，为所求的答案。
Sample Input
6
Sample Output
15
解题报告：
令 k｜n，m｜n gcd(m,n)=k , 令s(k)为gcd为k满足条件的m的个数。
gcd(m/k,n/k)=1, s(k)=euler(n/k)
ans=∑k*φ(n/k) (k|n)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL long long
LL n, ans;
LL phi( LL x ){LL m=sqrt(x+0.5);LL ans = x;for ( LL i=2; i<=m; i++) if( x%i==0 ){ans = ans/i*(i-1);while( x%i==0 ) x/=i;}if( x>1 ) ans = ans/x*(x-1);return ans;
}int main(){scanf("%lld", &n );ans = 0;for ( LL i=1; i*i<=n; i++ )if( n%i==0 ){ans+=(LL)i*phi(n/i);ans+=(LL)(n/i)*phi(i);}printf("%lld", ans);return 0;
}