a073. 輾轉相除法

Content

如果想要找最大公因數你會怎麼做呢？
你還在傻傻的用短除法嗎？嘖嘖，就讓我來教你一個快速簡單好玩有趣(?)的方法吧ˋˇˊ！！其實短除法也很好用喇QQ
你知道輾轉相除法嗎？
直接講可能你會不太懂，先直接上舉例
現在我們想要找$96, 78$的最大公因數
$96 \div 78 = 1...18$
$78 \div 18 = 4...6$
$18 \div 6 = 3...0$
運算結果：$96, 78$的最大公因數是$6$
也就是說把每運算過一次之後把：

除數變成下一行的被除數
餘數變成下一行的除數

一直計算到整除為止，這時除數就是兩個數字的最大公因數囉！
現在給你兩個數，請你計算出這兩個數的最大公因數是多少ㄅ><！

Input

輸入兩個正整數$a, b$

$1 \leq a, b \leq 2 \times 10^9$

Output

輸出一個正整數，為$a, b$的最大公因數

Sample Input #1

96 78

Sample Output #1

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1K
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

Hint ：

Tags:

出處:

[管理者：

yvonne852 (plum)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」