a738: 最大公約數

這篇教學會示範 ZeroJudge 基礎題庫「a738: 最大公約數」的解題過程。

題目需求

題目會提供兩個數字，透過程式求出這兩個數字的大公約數 ( 最大公因數 )。

題目連結：a738: 最大公約數

解答

參考「最大公因數 ( 多個數字 )」教學，只要透過「輾轉相除法」，就能夠得到最大公因數，但由於題目測試資料較龐大，可能會發生超時 ( TLE ) 的錯誤訊息，因此這題可以直接使用 Python math 標準函式中的 gcd 方法，來快速的計算出最大公因數。

參考：gcd(x, y)

import math
while True:
  try:
    a, b = map(int, input().split())   # 拆出兩個數字
    print(math.gcd(a, b))              # 計算最大公因數
  except:
    break

意見回饋

如果有任何建議或問題，可傳送「意見表單」給我，謝謝～