最大公约数之和——极限版II

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 gcd_extreme.in 输出文件 gcd_extreme.out

【题目描述】

输入正整数N，求G的值。G如下定义：

这里GCD(i,j)代表i,j的最大公约数。

对于不理解求和符号的人，下面给出了G的代码表示： 


G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
    G+=gcd(i,j);
}
/*gcd(i,j)的值是i,j的最大公约数*/


【输入格式】

输入包含至多100组数据。每组数据占一行，包含正整数N(2<=N<=1<N<4000000)。输入以N=0结束。

【输出格式】

对于每组数据，输出一行，即所对应的G值。答案保证在64位带符号整数范围内。

【样例输入】 

10
100
200000
0

【样例输出】 

67
13015
143295493160

【提示】

对于30%的数据，2<=N<=2000

对于100%的数据，2<=N<=4000000

【来源】

UVa11426 GCD - Extreme (II)

刘汝佳，《算法竞赛入门经典训练指南》表2.4