2元1次不定方程式とAtCoder ABC186 E-Throne（中編）

１．はじめに

前編では、2元1次不定方程式の解法について述べました。中編では、ユークリッドの互除法と、拡張ユークリッドの互除法の実装について書いていきます。

２．ユークリッドの互除法の実装

a と b の最大公約数を、gcd(a,b) と書くようにします。a を b で割った商を q ,あまりを r とすると、a=bq+r と書けます。このとき、gcd(a,b)=gcd(b,r) が成り立つという性質を用いたのが、ユークリッドの互除法でした。pythonで実装すると、次のようになります。　　

def gcd(a,b):
   if b==0:
       return a
   else:
       g=gcd(b,a%b)
       return g

gcd(a,0)=a なので、b=0 のとなったら、動作をやめて、最大公約数 a を返します。

３．拡張ユークリッドの互除法の実装

前編で2元1次不定方程式 216x+67y=1 の特殊解に x=21 , y=-68 があることを示しました。これは、ユークリッドの互除法を逆順に使うことで得られました。もう一度最大公約数をユークリッドの互除法を用いた計算を確認すると、gcd(216 , 67)=gcd(67 , 16)=gcd(16 , 3)=gcd(3 , 1) という手順で、最大公約数は 1 と分かりました。対応する不定方程式を順に書いていくと、216x+67y=1 , 67x+16y=1 , 16x+3y=1 , 3x+y=1 , となります。さて、3x+y=1の特殊解は、x=0 , y=1 とすぐに分かります。16x+3y=1 の特殊解に、x=1 , y=-5 があります。67x+16y=1 の特殊解に、x=-5 , y=21 があります。また、216x+67y=1 の特殊解に、x=21 , y=-68 があります。このような特殊解を得るアルゴリズムについて書いていきます。

s , t の2元1次方程式 as+bt=1 があり、a=bq+r から、gcd(a , b)=gcd(b , r)が成り立つことが分かり、対応する不定方程式 bx+ry=1…① が得られたとします。r=a-bq ですから、①は、bx+(a-bq)y=1 となり、ay+b(x-qy)=1 が得られます。as+bt=1 と係数を比較し、s=y…② , t=x-qy…③ が得られます。このとき、q は、a を b で割った商です。x , y の初期値を x=0 , y=1 とし、②、③を次々と適用すれば、ax+by=1 の特殊解が得られます。それを踏まえた python での実装例は、次のようになります。

def extgcd(a,b):
 if b==0:
   return a,1,0
 else:
   q,r=a//b,a%b
   g,x,y=extgcd(b,r)
   return g,y,x-q*y 

ここで、特殊解を求める部分については、ユークリッドの互除法を逆順にたどることになるので、特殊解を求める部分は、g,x,y=extgcd(b , r) よりも後に記述することになります。再帰関数の行きかけ順、帰りかけ順について、理解する必要があります。けんちょんさんの Qiita の記事、DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】が参考になります。

４．まとめ

中編では、ユークリッドの互除法と、拡張ユークリッドの互除法について書いてきました。次回（後編）は、ABC186 E-Throne を解くためにどうすれば良いか書いていきたいと思います。