TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

求兩數字的最大公因數,請練習實作輾轉相除法!

以下是輾轉相除法的說明:已知
$gcd(a, 0) = a$
$gcd(0, a) = a$
$gcd(a, b) = gcd(b, a\%b)$
所以我們可以不斷的用 $b$ 和 $a%b$ 當作新的 $a$ 和 $b$ 來求解,直到 $a$、$b$ 其中一個為 $0$ 為止。

Input Format

第一行有一個數字 $n$ ,表示接下來有 $n$ 行輸入 第 $2$ ~ $n+1$ 行每行有兩個數字 $a, b$,請求出 $a, b$ 的最大公因數。

Output Format

對每一行輸入輸出 $a, b$ 的最大公因數,共輸出 $n$ 行。

Sample Input 1

3
12 18
7 11
10 10

Sample Output 1

6
1
10

Hints

for python user: 請填入 ??? 的部分

n = int(input())
i = 0
while i < n:
    a, b = input().split()
    a = int(a)
    b = int(b)

    #Your code

    print(???) # 輸出結果(其中一個數字為0,另一個數字為答案)
    i += 1

Problem Source

NEOJ Problem 3021

Subtasks

No. Testdata Range Constraints Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 2
2 1000 65536 65536 3
3 1000 65536 65536 4
4 1000 65536 65536 5
5 1000 65536 65536 6
6 1000 65536 65536 7
7 1000 65536 65536 8
8 1000 65536 65536 9
9 1000 65536 65536 10