11417 GCD

題目連結

題目敘述

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

i與j的定義如下:
i的範圍為:1到N-1
j的範圍為:i+1到N
對每一組 (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;
    s for (int i = 1; i < N; i++) {
      for (int j = i + 1; j <= N; j++) {
        G += GCD(i, j);
      }
    }
    cout << G << endl;
  }
  return 0;
}