http://www.lydsy.com/JudgeOnline/problem.php?id=2705
Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一个整数，为N。
Output
一个整数，为所求的答案。
Sample Input
6
Sample Output
15
————————————————————————————————————————————
http://hzwer.com/3470.html的博客已经讲的蛮清楚了，这里在复述一遍。
gcd(i,n)的值显然是n的约数，这里取k=gcd(i,n)，满足该关系式的i的个数为s(k)。
则答案为∑k*s(k)（k|n）
又因为k=gcd(i,n)推出gcd(n/k,i/k)=1，设t=i/k，则n/k与t互质，求出t的个数。
这显然可以用欧拉函数解决，那么s(k)=phi(n/k)