输入正整数n,求gcd(1,2)+gcd(1,3)+gcd(2,3)+...+gcd(n-1,n)
设f(n) = gcd(1,n)+gcd(2,n)+...+gcd(n-1,n)
所求s(n) = f(2)+f(3)+...+f(n) = s(n-1)+f(n);
gcd(x,n) = i <=> gcd(x/i,n/i) = 1 满足条件的x/i有phi(n/i)个（欧拉函数）
可以按照素数筛选发那样做枚举因子i 然后f[n] += i*phi[n/i];
phi_table 用到了素数筛选发求出从1到n的欧拉函数只 存在phi[n]中
#include <cstdio>
#include <cstring>
const int maxn = 4000010;
typedef long long LL;
LL s[maxn], f[maxn], phi[maxn+10];
void phi_table(int n)
{
for(int i = 2; i <= n; i++)
phi[i] = 0;
phi[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!phi[i])
{
for(int j = i; j <= n; j += i)
{
if(!phi[j])
phi[j] = j;
phi[j] = phi[j] / i * (i-1);
}
}
}
}
int main()
{
phi_table(maxn);
memset(f, 0, sizeof(f));
for(int i = 1; i <= maxn; i++)
for(int n = i*2; n <= maxn; n += i)
f[n] += i * phi[n / i];
s[2] = f[2];
for(int n = 3; n <= maxn; n++)
s[n] = s[n-1] + f[n];
int n;
while(scanf("%d", &n), n)
printf("%lld\n",s[n]);
return 0;
}