c202 - 最大公因數(GCD)-TOI練習賽y7m5-4
題目描述
題目要求找出給定 n 個正整數的最大公因數 (GCD)。輸入包含 n 的值，以及 n 個以空白分隔的正整數。輸出這些數字的最大公因數。
解題思路
此題的核心是計算多個數字的最大公因數。可以使用貪心策略，從左到右依次計算兩個數字的 GCD，並用結果更新下一個數字。最終的結果就是所有數字的最大公因數。GCD 的計算使用歐幾里得演算法 (Euclidean Algorithm) 實現。如果過程中任何時候 GCD 變成 1，則可以直接輸出 1，因為 1 是任何數的公因數。
複雜度分析
- 時間複雜度: O(n * log(max_value))，其中 n 是數字的個數，max_value 是輸入數字的最大值。歐幾里得演算法的時間複雜度為 O(log(min(a, b)))，在最壞情況下，需要迭代 log(max_value) 次。
- 空間複雜度: O(n)，用於儲存輸入的數字陣列。
程式碼
#include <stdio.h>
long long int gcd(long long int a,long long int b){
if(b==0)return a;
return gcd(b,a%b);
}
int main(){
long long int a,ans=0;
scanf("%lld",&a);
long long int b[a];
for(int i=0;i<a;i++)
scanf("%lld",&b[i]);
for(int i=0;i<a-1;i++){
if(b[i]>b[i+1])
b[i+1]=gcd(b[i],b[i+1]);
else
b[i+1]=gcd(b[i+1],b[i]);
if(b[i+1]==1){
ans=1;
break;
}
}
if(ans)
printf("1");
else
printf("%lld",b[a-1]);
}