uva11424

maksyuki 发表于 oj 分类，标签:
12 9月 2015
0

Given the value of N, you will have to find the value of G. The definition of G is given below:G =i<N∑i=1j∑≤Nj=i+1GCD(i, j) Here GCD(i, j) means the greatest common divisor of integer i and integer j.

For those who have trouble understanding summation notation, the meaning of G is given in the following code:

G=0;

for(i=1;i<N;i++)

for(j=i+1;j<=N;j++)

{

G+=gcd(i,j);

}

/*Here gcd() is a function that finds

the greatest common divisor of the two

input numbers*/

Input

The input file contains at most 100 lines of inputs. Each line contains an integer N (1 < N < 4000001). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero.

Output

For each line of input produce one line of output. This line contains the value of G for the corresponding N. The value of G will fit in a 64-bit signed integer.

Sample Input

10

100

200000

0

Sample Output

67

13015

143295493160

 

题目类型：欧拉函数+预打表

算法分析：简单分析可知有求解G(n)的递推公式：G(n) = G(n - 1) + F(n) 边界G(0) = 0。其中F(n) = Sigma{gcd (i, n)}, 0 < i < n。而对于gcd (a, b) = 1, a < b来说，gcd (2 * a, 2 * b) = 2，gcd (3 * a, 3 * b) = 3，… gcd (k * a, k * b) = k，则每次从小到大求出b的欧拉函数值，之后直接F(k * b) += k * euler[b]，最后维护一个前缀和即可