今天來解YKL29(UVA11417)：GCD

GCD

找兩個數字之間的最大公因數

用a%b來縮小問題的規模

假設我們要計算 GCD(48, 18)：
48 % 18 = 12，所以問題轉化為 GCD(18, 12)
18 % 12 = 6，所以問題轉化為 GCD(12, 6)
12 % 6 = 0，此時返回 6，表示 GCD(48, 18) = 6

#include <iostream>
using namespace std;

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

}
int main(){
	int N;
	while(cin >> N){
		if(N==0)break;
		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;
	}
	return 0;
}

參考資料

https://blog.csdn.net/qq_35539831/article/details/122757946