题目链接：POJ2048
题意简述：给出一个整数N，求出 i 从1到 N 的所有 GCD(i,n) 的和。
解题思路：
将GCD（i，N）分为两个部分，即GCD（i，N）= 1与！=1。
- GCD（i，N） = 1：从1到N所有与N互素的数有 phi(N) 个，而如果数 i 与 N互素，那么GCD（i，N） = 1，故该部分的和就求出来了，就是phi(N)。
- GCD（i，N） ！= 1：假设GCD（i，N）= p；那么所有小于N的数中，尝试求出一共有多少个与N的最大公约数为 p 。N/p与N互素，小于 N/p 且与 N/p 互素的数 * p设为 j ，GCD（j，N）一定为p。所以GCD（i，N） = p 的数有 phi（N/p）个。
因此我们只需求出N的所有约数，即可求出最终答案。因为N的所有约数有对称性，故可以采用折半查找优化时间。
代码示例：
#include<cstdio>
typedef long long ll;
ll phi(ll n){
ll ans = n;
for(ll i = 2;i*i <= n;i++){
if(n%i == 0) ans = ans/i*(i-1);
while(n%i == 0) n/=i;
}
if(n > 1) ans = ans/n*(n-1);
return ans;
}
int main(){
ll n;
while(scanf("%lld",&n) != EOF){
ll ans = 0;
for(ll i = 1;i*i <= n;i++){
if(n % i == 0){
ans += phi(n/i)*i;
if(i * i < n) ans += phi(i)*(n/i);
}
}
printf("%lld
",ans);
}
return 0;
}