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

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file gcd_extreme.in Output file 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