# GCD
題目連結 [UVA 11417](https://onlinejudge.org/external/114/11417.pdf)

## 中文簡述
`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);
    
    }
/*Here GCD() is a function that finds
the greatest common divisor of the two
input numbers*/

## [think]

所以這題很簡單，之要寫一個GCD的副程式，在累加於G就可以了

## solution:

#include<iostream>
using namespace std;
int gcd(int a, int b) 
{
	if (a == 0 && b != 0) 
	{
		return a;
	}

	if (b == 0) 
	{
		return a;
	}
	else 
	{
		return gcd(b, a % b);
	}
}

int main()
{
	int G, i, j, n;
	while (cin >> n)
	{
		if (n == 0)
		{
			break;
		}
		G = 0;
		for (i = 0; i < n; i++)
		{
			for (j = i + 1; j <= n; j++)
			{
				G += gcd(i, j);
			}
		}
		cout << G << endl;
	}

}

###### tags: `UVA`
回目錄 [學習筆記](/gIBZqAbWTCis7uOPp149gA)