d255 - 11417 - GCD
題目描述
題目要求計算 G 的值，G 定義為所有 1 < i < N 且 i < j <= N 的 GCD(i, j) 的總和。輸入為多個 N 值，直到輸入為 0 為止。
解題思路
題目採用暴力解法，對於每個輸入的 N，使用兩層迴圈遍歷所有可能的 i 和 j 的組合，計算 GCD(i, j) 並將其加到 G 中。GCD 的計算使用遞迴的歐幾里得演算法。程式首先讀取 N，如果 N 不為 0，則計算 G，並將結果輸出。如果 N 為 0，則程式結束。
複雜度分析
- 時間複雜度: O(N^2 * log(N))。外層兩層迴圈是 O(N^2)，而 GCD 的計算（歐幾里得演算法）的時間複雜度是 O(log(N))。
- 空間複雜度: O(1)。程式只使用了常數級別的額外空間。
程式碼
#include <iostream>
using namespace std;
int GCD(int m, int n) {
if(n == 0)
return m;
else
return GCD(n, m % n);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int G,N=0;
while(cin >> N){
if(N!=0){
G+=N-1;
for(int i=2;i<N;i++){
for(int j=i+1;j<=N;j++){
if(i==2&&j%2!=0){
G++;
}
else
if(j-i==1){
G++;
}
else
G+=GCD(i,j);
}
}
cout << G << endl;
G=0;
}
else{
return 0;
}
}
}