24h購物| | PChome| 登入
2011-06-07 17:27:16| 人氣988| 回應0 | 上一篇 | 下一篇

d807. 方方

推薦 0 收藏 0 轉貼0 訂閱站台

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

提示 :

出處 :

(管理:shik)

作法 : 求 gcd(n,m)

/**********************************************************************************/
/*  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;
}

台長: Morris
人氣(988) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:d808. 黑暗部落
此分類上一篇:d655. 許胖公仔

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文