a158 - 11827 - Maximum GCD
題目描述
題目要求給定一組正整數，找出其中所有數字對的最大公因數 (GCD)。
解題思路
此題採用暴力法。對於每組輸入，首先讀取數字並儲存在陣列中。然後，使用兩層迴圈遍歷所有可能的數字對，計算每一對的 GCD，並更新最大 GCD 值。GCD 的計算使用遞迴的歐幾里得演算法。
複雜度分析
- 時間複雜度: O(n^2 * log(max_val))，其中 n 是數字的數量，max_val 是陣列中最大的數字。外層迴圈和內層迴圈都是 O(n^2)，而 GCD 的計算（歐幾里得演算法）的時間複雜度是 O(log(max_val))。
- 空間複雜度: O(n)，用於儲存輸入數字的陣列。
程式碼
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int GCD(int m,int n){
if(m%n==0)
return n;
return GCD(n,m%n);
}
int main(){
int a;
cin >> a;
string b;
getline(cin,b);
while(a--){
getline(cin,b);
int M[101]={},i=0,max=0;
stringstream ss;
ss<<b;
while(1){
ss>>M[i];
i++;
if(ss.fail()) break;
}
for(int i=0;M[i]!=0;i++){
for(int j=i+1;M[j]!=0;j++){
if(M[i]>M[j]){
if(GCD(M[i],M[j])>max)
max=GCD(M[i],M[j]);
}
else{
if(GCD(M[j],M[i])>max)
max=GCD(M[j],M[i]);
}
}
}
cout << max << endl;
}
}