d807 - 方方

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個長寬為 n 和 m 的長方形，經過反覆切割最大正方形的過程，最終剩餘的正方形的大小。切割策略是每次都從剩餘區域中切割出最大的正方形。

解題思路

這個問題的關鍵在於觀察切割過程。每次切割最大正方形後，剩餘的部分仍然是一個長方形。這個過程會持續進行，直到剩餘的部分本身就是一個正方形。最終的正方形的大小，實際上就是原始長方形長寬的最大公約數 (GCD)。

例如，如果 n = 5, m = 2，第一次切割出 2x2 的正方形，剩下 3x2 的長方形。第二次切割出 2x2 的正方形，剩下 1x2 的長方形。第三次切割出 1x1 的正方形，剩下 1x1 的正方形。最終的正方形大小是 1，也就是 5 和 2 的最大公約數。

因此，只需要計算 n 和 m 的最大公約數即可。可以使用歐幾里得演算法 (Euclidean Algorithm) 來高效地計算 GCD。

複雜度分析

• 時間複雜度: O(log(min(n, m))) 歐幾里得演算法的時間複雜度取決於輸入數字的大小，最壞情況下與輸入數字的位數成正比。
• 空間複雜度: O(1) 演算法使用常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
int GCD(int m,int n){
	if(m%n==0)
		return n;
	else
		return GCD(n,m%n);
} 
int main(){
	int a,b;
	while(cin >> a >> b){
		if(a>b)
			cout << GCD(a,b) << endl;
		else
			cout << GCD(b,a) << endl;
	}
}