a738. 最大公约数 - 高中生程式解題系統

a738. 最大公约数

標籤 : GCD 最大公因數
通過比率 : 5417人/5921人 ( 91% ) [非即時]
評分方式：

Tolerant

最近更新 : 2013-08-09 22:17

內容

小海豚要上初中了，也会了一点程序设计。海豚爸爸想起大约30年前上高一的时候自己第一次摸电脑。现在难以想象一下那种心情，那时候一个中国大陆一个大学毕业生（很稀罕的哦）月工资只有60元RMB，而一台苹果II要6000元RMB。海豚爸爸有生以来输入电脑的第一个程序，就是“最大公约数”。

輸入說明

每行2个数a, b 0 < a, b < 1000000000

EOF结束

輸出說明

对每对 a,b 输出其最大公约数

範例輸入 #1

30 24
2 4

範例輸出 #1

6
2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (50%): 1.0s , <1K
公開測資點#1 (50%): 1.0s , <1K

提示：

“辗转相除法”，又称“欧几里德算法”。比如计算 30 和 24 的最大公约数：

30除以24，余6 --> 24除以6，余0 --> 得到最大公约数就是 6

標籤:

GCD 最大公因數

出處:

海豚原创

本題狀況本題討論排行