回分類題庫
c040: 3.輾轉相除法
關鍵字: 107校內初賽

測資點 : 10 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 924 Times / 778 Users | Submit : 1438 Times / 804 Users | Accepted rate : 97%
題目加入時間 : 2018-08-09 22:38

Content: 简体中文

輾轉相除法,又稱歐幾里得算法,是一種求最大公因數的算法,假設有兩個正整數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。

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

Input:

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

Output:

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

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
96 40

輸入2:
35 6

Sample Output :

輸出1:
96%40=16
40%16=8
16%8=0
GCD(96,40)=8

輸出2:
35%6=5
6%5=1
5%1=0
GCD(35,6)=1

Hint :

Author :

107校內初賽 (管理員:sagit)

  Solve it!   Status Forum