a738: 最大公约数
Tags : GCD 最大公因數
Accepted rate : 4421人/4857人 ( 91% ) [非即時]
評分方式:
Tolerant

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

Content

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

Input

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

EOF结束

Output
对每对 a,b 输出其最大公约数
Sample Input #1
30 24
2 4
Sample Output #1
6
2
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
Hint :

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

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

Tags:
GCD 最大公因數
出處:
海豚原创


ID User Problem Subject Hit Post Date
30127 10730094@ms2...(給開司一份薯片) a738
163 2022-04-30 13:49
30126 10730094@ms2...(給開司一份薯片) a738
129 2022-04-30 13:36
30125 10730094@ms2...(給開司一份薯片) a738
173 2022-04-30 13:29
29420 lee1030075@g...(hi) a738
265 2022-02-27 16:27
28829 oxxostudio(oxxo.studio) a738
Python 解答
271 2022-01-06 17:23