拡張ユークリッド互除法

別解（繰り返し、MAT文による）

!拡張ユークリッド互除法

!「a*x+b*y=GCD(a,b)となるxとyが存在する」

!補助式
!　a*x1+b*y1=z1
!　a*x2+b*y2=z2
!を考える。
!z1/z2の商Q、余りRと置くと、z1=Q*z2+R。
!したがって、R=z1-Q*z2=a*x1+by1 - Q*(a*x2+b*y2)=a*(x1-Q*x2) + b*(y1-Q*y2)。
!ここでa*x3+by3=z3と比較して、
!x3=x1-Q*x2, y3=y1-Q*y2, z3=R=z1-Q*z2

INPUT PROMPT "２つの正の整数": a,b

DIM v1(3),v2(3),v3(3)
LET v1(1)=1 !x1
LET v1(2)=0 !y1
LET v1(3)=a !z1

LET v2(1)=0 !x2
LET v2(2)=1 !y3
LET v2(3)=b !z3

DO UNTIL v2(3)=0 !z2=0まで
LET Q=INT(v1(3)/v2(3)) !z1/z2の商

DIM t(3) !(x3,y3,z3)=(x1,y1,z1)-Q*(x2,y2,z2)
MAT t=Q*v2
MAT v3=v1-t

MAT v1=v2 !(x1,y1,z1)=(x2,y2,z2)

MAT v2=v3 !(x2,y2,z2)=(x3,y3,z3)
LOOP

PRINT "x,y,GCD(a,b)"
MAT PRINT v1

END

拡張ユークリッド互除法	返事を書くノートメニュー
山中和義 <drdlxujciw> 2008/01/08 11:40:31 ** この記事は1回修正されてます
!問い !29リットル入るバケツと17リットル入るバケツがある。 !この2つのバケツを使って、別のバケツに1リットルの水を入れる。 !答え !17リットルのバケツで12回くみ入れた後、29リットルのバケツで7回くみ出す LET a=17 LET b=29 CALL ExGCD(a,b ,s,t,c) PRINT s;"";a;" + ";t;"";b;"=";c END EXTERNAL SUB ExGCD(a,b, s,t,c) !a>0,b>0 に対して sa+tb=c となる s,t,c=Gcd(a,b) を求める IF b=0 THEN LET s=1 LET t=0 LET c=a ELSE LET q=INT(a/b) !Qi　※Rk-1 = QkRk + Rk+1より LET r=MOD(a,b) !Ri CALL ExGCD(b,r, u,v,c) !k=n-1,…,3,2 まで続ける LET s=v LET t=u-vq END IF END SUB samplesフォルダ内EUCLID.BAS参照

Re: 拡張ユークリッド互除法	返事を書くノートメニュー
山中和義 <drdlxujciw> 2008/01/10 16:10:41
別解（繰り返し、MAT文による） !拡張ユークリッド互除法 !「ax+by=GCD(a,b)となるxとyが存在する」 !補助式 !　ax1+by1=z1 !　ax2+by2=z2 !を考える。 !z1/z2の商Q、余りRと置くと、z1=Qz2+R。 !したがって、R=z1-Qz2=ax1+by1 - Q(ax2+by2)=a(x1-Qx2) + b(y1-Qy2)。 !ここでax3+by3=z3と比較して、 !x3=x1-Qx2, y3=y1-Qy2, z3=R=z1-Qz2 INPUT PROMPT "２つの正の整数": a,b DIM v1(3),v2(3),v3(3) LET v1(1)=1 !x1 LET v1(2)=0 !y1 LET v1(3)=a !z1 LET v2(1)=0 !x2 LET v2(2)=1 !y3 LET v2(3)=b !z3 DO UNTIL v2(3)=0 !z2=0まで LET Q=INT(v1(3)/v2(3)) !z1/z2の商 DIM t(3) !(x3,y3,z3)=(x1,y1,z1)-Q(x2,y2,z2) MAT t=Qv2 MAT v3=v1-t MAT v1=v2 !(x1,y1,z1)=(x2,y2,z2) MAT v2=v3 !(x2,y2,z2)=(x3,y3,z3) LOOP PRINT "x,y,GCD(a,b)" MAT PRINT v1 END