# UVA 11417 GCD
## 題目連結 [UVA 11417](https://vjudge.net/problem/UVA-11417)
### 題目內容
Given the value of N, you will have to find the value of G. The definition of G is given below:
$$G=\sum_{i=1}^{i<N} \sum_{j=i+1}^{j \leq N} GCD(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*/
### 輸入限制
The input is a file such that each line contains a positive number. A line containing the number 0 is the end of the input. The given numbers can contain up to 1000 digits.
### 輸出限制
The output of the program shall indicate, for each input number, if it is a multiple of nine, and in case it is, the value of its nine-degree. See the sample output for an example of the expected formatting of the output.
### 解題思路
1.GCD函式是計算最大公因數
2.G為加1到n兩兩最大公因數的和
### 程式碼

#include<bits/stdc++.h>
using namespace std;
int n;
int GCD(int a,int b){
    while(a!=0 && b!=0){
        if(a>=b){
            a=a%b;
        }
        else if(b>a){
            b=b%a;
        }
    }
    if(a>=b){
        return a;
    }
    else{
        return b;
    }
}
int main(){
    while(cin>>n &&n!=0){
        int G=0;
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                G+=GCD(i,j);
            }
        }
        cout<<G<<endl;
    }
}

## 測資
### Sample input
10
100
500
0
### Sample output
67
13015
442011
## 中文題目連結 [zerojudge d255](https://zerojudge.tw/ShowProblem?problemid=d255)