拡張ユークリッドの互助法の応用

ax+by=cがa!=0、b!=0、c!=0のとき、
x,yが整数解を持つ条件は、
cがgcd(a,b)で割り切れることである。

a,b,cのいずれかが0である。
もしくは、cがgcd(a,b)で割り切れない場合、
場合分けが必要となる。

すなわち、ax+by=k*gcd(a,b)であれば、
x,yは整数解を持つ。

以下の関数extgcdはax+by=gcd(a,b)のとき、
複数あるx,yの1つの解を求める。

long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}

ax+by=k*gcd(a,b)であるとき、
複数ある1つの解はax+by=gcd(a,b)の解に、
それぞれkを乗じたものである。

例えば、
12x+9y=6のとき、
gcd(12,9)=3であり6は3で割り切れるので、
x,yは整数解を持つ。
ax+by=gcd(a,b)を解くとx=1,y=-1である。
よって、12x+9y=6のとき、
x=2,y=-2が1つの解として求められる。

これを、12*(x-2)+9*(y+2)=0と書き換える。
変形して、(x-2)/3=-(y+2)/4となる。

ここでxに3を足したときyから4を引けば、
この式は常に成り立つ。

よって、
x=3t+2
y=-4t-2
という一般式を立てることができる。

例題

1次元のp軸がある。
A君はp=5の地点にいて正の方向に4ずつ進める。
B君はp=13の地点にいて正の方向に6ずつ進める。
A君とB君が同じ地点にいるときの、
最も最短の位置はどこか？

まず、式を立てる。

4x+5=6y+13

変形して、

4x-6y=8

4x-6y=-2のときx=1,y=1となる。

よって、4x-6y=8の1つの解は、
x=-4,y=-4である。

一般式は、

x=3t-4
y=2t-4

と書ける。

x>=0,y>=0なので、
t>=2のときに条件を満たす。
最短を求めるのでt=2のとき、
x=2,y=0となり
最短でp=13の地点で同じ地点にいる。