2011-06-07 17:27:16Morris
d807. 方方
http://zerojudge.tw/ShowProblem?problemid=d807
內容 ：
在一個遙遠的國度裡，每個村莊都是長方型的，雖然有時候會很不方便
但是大家還是過著快樂的日子。直到有一天，有個異地來的軍隊，想要佔領各個村莊
他們佔領的方式是，從村莊裡頭，切出一個儘可能大的正方形，先佔為己有
隔日，在從未佔領的部分，重複這樣的動作。
直到某一天，未佔領的部分為一個正方形的時候，就結束佔領的動作。
現在我們想知道，最後的那一個正方形是多大？（見圖）
輸入說明
：
給定兩個正整數 n,m 表示村莊的長寬。n,m皆介於 1 ~ 10^9
包含多筆測試資料。
包含多筆測試資料。
輸出說明
：
輸出，最後的正方形大小
範例輸入 ：
5 5 2 1 2 2 10 5 13 9
範例輸出 ：
5 1 2 5 1
提示
：
出處
：
/**********************************************************************************/
/* Problem: d807 "方方" from */
/* Language: C */
/* Result: AC (2ms, 264KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-02 22:15:31 */
/**********************************************************************************/
#include<stdio.h>
int gcd(int x, int y) {
int t;
while(x%y) {
t = x, x = y, y = t%y;
}
return y;
}
main() {
int n, m;
while(scanf("%d %d", &n, &m) == 2) {
printf("%d\n", gcd(n, m));
}
return 0;
}
上一篇：d655. 許胖公仔
下一篇：d808. 黑暗部落