Petitverse

一瞬フェルマーの最終定理かと思って「絶対解けんやん」って思ったけど全然違った()

全通り試せばいける。(ネタ解答)
SW=0
IF A<B THEN SWAP A,B:SW=1
FOR X=0 TO B-1
　IF (C-A*X) MOD B==0 THEN
　　Y=(C-A*X) DIV B
　　IF SW THEN ?Y,X ELSE ?X,Y
　　END
　ENDIF
NEXT
?"解は無い"

結局誰もやらなさそうなのでやります。
(答えだけ載せても分かりづらいと思って解説書いたらめっちゃ長くなった。)

まず自分で解く場合。
例えば a=37,b=13,c=6 とします
(a=11だとユークリッドがすぐ終わってわかりづらかった)
つまり 37x+13y=6 をみたす x,y を1つ求めます。
まずユークリッドの互除法を使います。
37 = 13*2 + 11 ...�@
13 = 11*1 + 2 ...�A
11 = 2*5 + 1 ...�B
2 = 1*2　(終わり)

ここで、�@〜�Bを使って、1 = 37*□ + 13*□ を作ります。
(1 = の部分は、互除法が終わる直前の余りの値にする)

�B→�A→�@の順に計算する場合、
1 = 11 - 2*5　(← 2 の部分に�Aを使う)
　= 11 - (13 - 11*1)*5
　= 13*(-5) + 11*6　(← 11 の部分に�@を使う)
　= 13*(-5) + (37 - 13*2)*6
　= 13*(-17) + 37*6

�@→�A→�Bの順に計算する場合、
11 = 37 - 13*2 ...�@'
2 = 13 - (37 - 13*2)*1　(←�Aに�@'を使った)
　= 37*(-1) + 13*3 ...�A'
1 = (37 - 13*2) - (37*(-1) + 13*3)*5　(←�Bに�@'と�A'を使った)
　= 37*6 + 13*(-17)

c=6 なので、6 = にする必要があります。
なので両辺6倍して、 6 = 37*36 + 13*(-102)
よって (x,y) = (36,-102)
(整数倍してcにならない場合は、x,yは存在しないことになります。)

上でやったことを一般化します。
つまり、具体的な数字の代わりに文字(変数)を使って同じことをやります。
ユークリッドの互除法のn回目で出てきた余りをR_nとすると、
R_(n-2) = R_(n-1) * D_n + R_n ...�C
と表せます。
このとき、
D_n = R_(n-2) div R_(n-1)
R_n = R_(n-2) mod R_(n-1)
で計算できます。(div, mod はプチコンのそれ)

(続く)

(続き)
もう一つ必要なのは r = a*□ + b*□ を作る式です
上で計算した例では2通りの順番で計算しましたが、
プログラムでやる場合は�@→�A→�Bの順で計算したほうがよさそうです。
(�B→�A→�@だと、互除法を全部計算してからなので、�@�A�Bの結果とかを全部配列とかに入れておかないと計算できません)
n番目の式まで計算した結果を
R_n = A * X_n + B * Y_n
と表せたとすると、
さっき書いた互除法の一般式�CのR_(n-1)とR_(n-2)のところにこれを代入すれば、
R_n = R_(n-2) - R_(n-1) * D_n
　= (A * X_(n-2) + B * Y_(n-2)) - (A * X_(n-1) + B * Y_(n-1)) * D_n
　= A * (X_(n-2) - X_(n-1) * D_n) + B * (Y_(n-2) - Y_(n-1) * D_n)
と表せます。
よって、
X_n = X_(n-2) - X_(n-1) * D_n
Y_n = Y_(n-2) - Y_(n-1) * D_n
と計算できます。

次に必要なのは初期値。
つまり、R_0 を計算するのに R_(-1), R_(-2) が必要なのでこれをセットします。
A = B * D_0 + R_0 なので、
R_(-2) = A, X_(-2) = 1, Y_(-2) = 0
R_(-1) = B, X_(-1) = 0, Y_(-1) = 1
となります。

最後に計算が終わる時の処理です。
R_n = 0 になったら計算終わりです。
(R_(n-1) がAとBの最大公約数になる)
R_(n-1) = A * X_(n-1) + B * Y_(n-1) より、
左辺がCになるように両辺 C / R_(n-1) を掛ければ、
C = A * (X_(n-1) * C / R_(n-1)) + B * (Y_(n-1) * C / R_(n-1))
なので、答えは
X = X_(n-1) * C / R_(n-1)
Y = Y_(n-1) * C / R_(n-1)

以上のことをプログラムで書くとこうなります。
R,X,Yなどは配列変数を用意しなくても、
R_0, R_(-1), R_(-2) を普通の変数で用意して、
R_0の計算が終わったら R_0→R_(-1)→R_(-2) と中身を移動していけばいいですね。
Dについては計算途中に D_n を1つ使うだけなので D_(-1) や D_(-2) は不要です。

R2=A:X2=1:Y2=0
R1=B:X1=0:Y1=1
WHILE 1
　D0=R2 DIV R1
　R0=R2 MOD R1
　IF R0==0 THEN BREAK
　X0=X2-X1*D0
　Y0=Y2-Y1*D0
　R2=R1:R1=R0
　X2=X1:X1=X0
　Y2=Y1:Y1=Y0
WEND
X=X1*C/R1
Y=Y1*C/R1
?X,Y