求兩數字的最大公因數,請練習實作輾轉相除法!
以下是輾轉相除法的說明:已知
$gcd(a, 0) = a$
$gcd(0, a) = a$
$gcd(a, b) = gcd(b, a\%b)$
所以我們可以不斷的用 $b$ 和 $a%b$ 當作新的 $a$ 和 $b$ 來求解,直到 $a$、$b$ 其中一個為 $0$ 為止。
第一行有一個數字 $n$ ,表示接下來有 $n$ 行輸入 第 $2$ ~ $n+1$ 行每行有兩個數字 $a, b$,請求出 $a, b$ 的最大公因數。
對每一行輸入輸出 $a, b$ 的最大公因數,共輸出 $n$ 行。
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
NEOJ Problem 3021
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 |