a738 - 最大公约数
題目描述
題目要求計算兩個整數 a 和 b 的最大公約數 (GCD)。輸入為多組 a 和 b 的值，直到輸入結束 (EOF)。
解題思路
本題使用輾轉相除法（歐幾里德演算法）來計算最大公約數。輾轉相除法的原理是：兩個整數的最大公約數等於其中較小的數和兩數相除餘數的最大公約數。不斷重複這個過程，直到餘數為 0，則最後的除數即為最大公約數。程式碼中先判斷 a 和 b 的大小關係，然後進行迭代計算，直到餘數為 0。
複雜度分析
- 時間複雜度: O(log(min(a, b)))
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int main(){
long long int a;
long long int b;
long long int i;
while(cin >> a >> b){//30//24
if(a>b){
i=a;
while(i>0){
a%=b;
i=a;
if(i==0){
cout << b << endl;
break;
}
if(i>0){
b%=a;
i=b;
if(i==0){
cout << a << endl;
break;
}
}
}
}
if(b>a){
i=b;
while(i>0){
b%=a;
i=b;
if(i==0){
cout << a << endl;
break;
}
if(i>0){
a%=b;
i=a;
if(i==0){
cout << b << endl;
break;
}
}
}
}
if(a==b){
cout << a;
}
}
}