d693 - 最小公倍數

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 n 個正整數的最小公倍數 (LCM)。輸入首先是一個整數 n，表示接下來有 n 個正整數。當 n 為 0 時，程式結束。

解題思路

這題的核心是利用最大公因數 (GCD) 來計算最小公倍數。兩個數的 LCM 可以通過公式 LCM(a, b) = (a * b) / GCD(a, b) 計算。對於多個數，可以迭代地計算 LCM。例如，對於 a, b, c 三個數，可以先計算 LCM(a, b)，然後計算 LCM(LCM(a, b), c)。

程式碼中，首先定義了一個計算 GCD 的函數 gcd()，使用歐幾里得演算法。然後，在主函數中，讀取 n 和 n 個正整數，並使用迴圈迭代地計算這些數的 LCM。迴圈從第二個數開始，每次將當前的 LCM 與下一個數計算 LCM，並更新 LCM 的值。最後，輸出最終的 LCM。

複雜度分析

• 時間複雜度: O(n * log(max_val))，其中 n 是輸入的數字個數，max_val 是輸入數字的最大值。log(max_val) 是歐幾里得演算法計算 GCD 的時間複雜度，迴圈執行 n-1 次。
• 空間複雜度: O(n)，用於儲存輸入的 n 個數字。

程式碼

#include <iostream>

using namespace std;

int gcd(long long int m, long long int n) { 
    if(n == 0) 
        return m; 
    else 
        return gcd(n, m % n); 
}

int main(){
	int a=0;
	while(cin >> a){
		if(a!=0){
			long long int b[a];
			for(int i=0;i<a;i++){
				cin >> b[i];
			}
			for(int i=0;i<a-1;i++){
				b[i+1]=(b[i]*b[i+1])/gcd(b[i],b[i+1]);
			}
			cout << b[a-1] << endl;
		}
	}
}