a738- - GCD

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算輸入的兩個整數的最大公因數 (GCD)。輸入為多組數字，每行包含兩個整數 a 和 b，程式需要輸出 a 和 b 的 GCD。

解題思路

此題可以使用歐幾里得演算法 (Euclidean Algorithm) 來計算兩個整數的最大公因數。歐幾里得演算法基於以下原理：兩個整數的最大公因數等於其中較小的數和兩數相除餘數的最大公因數。此過程重複進行，直到餘數為零，則較小的數即為最大公因數。C++ 標準庫 <algorithm> 提供了 std::__gcd 函數，可以直接使用。

複雜度分析

• 時間複雜度: O(log(min(a, b))) 歐幾里得演算法的時間複雜度與輸入數字的大小有關，最壞情況下與 log(min(a, b)) 成正比。
• 空間複雜度: O(1) 程式只使用了常數級別的額外空間。

程式碼

#include <iostream>
#include <algorithm>

using namespace std;

int main (){
	int a,b;
	while(cin >> a >> b){
		cout << std::__gcd(a,b) << endl;
	}
	
}