GCDEX - GCD Extreme
题意翻译
### 题目描述
得定 $n$ ,求
$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\gcd(i,j)$$
其中 $\gcd(i,j)$ 指的是 $i$ 和 $j$ 的最大公约数。
### 输入格式
**本题有多组数据。**
对于每组数据,输出一个整数 $n$ ,如果 $n=0$ 就终止程序。
### 输出格式
对于每组数据,输出计算结果。
### 说明 / 范围
对于 $100\%$ 的数据,$1 \le n \le 10^6$,不超过 $20000$ 组数据。
题目描述
Given the value of N, you will have to find the value of G. 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.
输入输出格式
输入格式
The input file contains at most 20000 lines of inputs. Each line contains an integer N (1 < N < 1000001). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero.
输出格式
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.
输入输出样例
输入样例 #1
10
100
200000
0
输出样例 #1
67
13015
143295493160
Time limit has been changed. Some AC solutions get TLE