e793 - an easy gcd problem

🔗 前往 ZeroJudge 原題

題目描述

題目要求實作一個 C++ 程式，計算兩個長整數的最大公因數 (GCD)，且限制不能使用分支、條件判斷、迴圈等控制流程結構，僅能使用基本的算術運算符和輸入輸出。輸入為多組數字對，以 a = b = 0 作為結束標記。

解題思路

此題的核心是使用歐幾里得演算法 (Euclidean Algorithm) 計算 GCD。歐幾里得演算法基於以下原理：兩個整數的最大公因數等於其中較小的數和兩數相除餘數的最大公因數。 程式使用迭代的方式實現此演算法，直到餘數為 0，此時被除數即為最大公因數。由於題目限制不能使用迴圈，演算法的迭代透過 while(b) 實現，利用 b 的真偽性來控制迭代的進行。

複雜度分析

• 時間複雜度: O(log(min(a, b)))
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
long long a,b,t;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> a >> b){
		if(a==0&&b==0)break;
        while(b){
            t = b;
            b = a%b;
            a = t;
    	}
		cout << a << "\n";
	}
}