b112 - 5. 高中運動會
題目描述
題目要求計算給定 N 個學校的人數，最多可以分成多少個隊伍，每個隊伍的人數必須相同，且所有學校的人數都必須能被隊伍人數整除。換句話說，題目要求計算 N 個數字的最大公因數 (GCD)。
解題思路
這題的核心是求出 N 個數字的最大公因數。程式碼使用迭代的方式，從第二個數字開始，每次計算目前結果與下一個數字的 GCD，並用新的 GCD 更新結果。最終的結果就是所有數字的最大公因數。GCD 的計算使用歐幾里得演算法 (Euclidean Algorithm)。如果只有一個學校，則直接輸出該學校的人數。
複雜度分析
- 時間複雜度: O(N * log(M))，其中 N 是學校的數量，M 是人數的最大值。歐幾里得演算法的時間複雜度為 O(log(M))，而迭代遍歷所有學校需要 O(N) 的時間。
- 空間複雜度: O(N)，用於儲存每個學校的人數。
程式碼
#include <iostream>
using namespace std;
int gcd(long long int n, long long int m) {
if(m == 0)
return n;
else
return gcd(m, n % m);
}
int main(){
long long int a=0;
while(cin >> a){
long long int b[a];
for(int i=0;i<a;i++){
cin >> b[i];
}
if(a==1){
cout << b[0] << endl;
}
else{
for(int i=0;i<a-1;i++){
b[i+1]=gcd(b[i],b[i+1]);
}
cout << b[a-1] << endl;
}
}
}