擴充最大公因數

擴充最大公因數

程式編日期: 2009年9月9日

程式可以計算兩個正整數a及b的最大公因數及求不定方程 ax + by =GCD(a, b)的一個整數解。第一個程式較簡短，但程式需要在BASE模式執行，操作較不便(完結後需後按MODE 1返回正常計算模式)，第二個程式較長但在COMP模式執行，容許輸入的數值亦較大。

第一個程式 (75 bytes)

程式需要在 BASE 模式下執行，因此在選擇新程式位置後，按 3 選用BASE模式。

ClrMemory: Dec: ?→A: ?→B: A→C: B→D: 1→X:

While B: Y→M: X - A ÷ BY→Y: M→X: B→M:

A - A ÷ BB→B: M→A: WhileEnd: M◢

X◢ M - CX: Ans ÷ D

第二個程式 (COMP模式，85 bytes)

?→A: ?→B: A→C: B→D: Pol( 1 , 0: Fix 0: While B:

Y→M: X - YRnd( A÷B - . 5→Y: M→X: B→M:

A - B Rnd( A÷B - . 5→B: M→A: WhileEnd:

Norm 1: M◢ X◢ D^-1(M - CX

註: 輸入的數值必須為正整數，否則答案錯誤。

例題: 找48及60的最大公因數及滿足不定方程 48x + 60y = GCD(48, 60)。

按 Prog 1 再按 48 EXE 60 EXE (顯示最大公因數為12)

EXE (顯示 x為 -1) EXE (顯示 y為1)

註: 若果是第一個程式，計算完結後按 MODE 1終止及返回正常計算模式