d040. 3.輾轉相除法 - 程式闖關解題系統

內容

輾轉相除法，又稱歐幾里得算法，是一種求最大公因數的算法，假設有兩個正整數A、B且A>B，而A除以B的餘數為C，則A、B的最大公因數和B、C的最大公因數相同，接下來再以B除以C的餘數為D，則C、D的最大數因數也和前面的B、C的最大公因數以及A、B的最大公因數相同。如此反覆運作，直到餘數變成0時，則前一個步驟中較小的數字即為最大公因數。例如96和40，96%40=16、40%16=8、16%8=0，則96和40的最大公因數為8。

現在給你兩個正整數，請你以輾轉相除法計算出他們的最大公因數為多少。

輸入說明

輸入兩個正整數 A、B (A>=B)，即要求最大公因數的兩個數。

輸出說明

請依照下面範例輸出的格式，印出輾轉相除法每個過程，最後再印出這兩個數字的最大公因數是多少。

範例輸入 #1

96 40

範例輸出 #1

96%40=16
40%16=8
16%8=0
GCD(96,40)=8

範例輸入 #2

35 6

範例輸出 #2

35%6=5
6%5=1
5%1=0
GCD(35,6)=1

測資資訊：

記憶體限制： 64 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

提示：

標籤:

GCD 迴圈

出處:

中女107 [管理者：

sagit (sagit)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」