11417 GCD

題目連結

題目敘述

給定一個整數 N，我們定義 G 為從 1 到 N 中，所有兩兩不同的整數組合 i 和 j（其中 i < j）的最大公因數（GCD）的總和

i與j的定義如下: i的範圍為 1N-1 j的範圍為 i+1N 對每一組 (i,j)，計算 GCD(i,j) 將所有的 GCD(i, j) 相加，總和就是 G

輸入說明

每一行包含一個整數 N，代表需要計算 G 的上限值 當輸入為 0 時表示結束，此行不需處理 輸入最多包含 100 行 1 < N < 501

輸出說明

對於每一個輸入的 N，輸出一行對應的 G 值

解題思路

利用輾轉相除法的遞迴函式，用來計算兩個數的最大公因數

程式碼

#include <iostream>
using namespace std;

int GCD(int a,int b){
    if(a==0)return b;
    return GCD(b%a,a);
}

int main(){
    int N;
    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;
    }
    return 0;
}