第一课堂
Current course
Participants
General
Topic 2
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
最大公约数之和——极限版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
【来源】
刘汝佳,《算法竞赛入门经典训练指南》表2.4