まず、\(g=\gcd(A,B)>1\) である場合明らかに \(X,Y\) 共に \(g\) の倍数である必要があります。さらに、この場合 \(A,B,X,Y\) 全て \(g\) で割った値に置き換えても答えは変わりません。この置換により以降は \(\gcd(A,B)=1\) の場合を考えます。

\(|x-x'|=A\) かつ \(|y-y'|=B\) を満たす座標に移動させる操作を操作 \(1\)、\(|x-x'|=B\) かつ \(|y-y'|=A\) に移動させる操作を操作 \(2\) と呼びます。

まず、操作 \(1\) と操作 \(2\) を行う回数の偶奇を固定します。操作 \(1\) を行う回数を \(\bmod 2\) で \(c_1\ (\in \lbrace 0,1\rbrace)\) と固定すると、操作 \(1\) を行うことにより増える \(x\) 座標の値は整数 \(x_1\) を用いて \((2x_1+c_1)A\)、操作 \(2\) を行うことにより増える \(y\) 座標の値は整数 \(y_1\) を用いて \((2y_1+c_1)B\) と表されます。また、操作 \(1\) のみを用いて \(x,y\) 座標をそれぞれ \((2x_1+c_1)A,\ (2y_1+c_1)B\) だけ増やすために必要な操作回数の最小値は \(\max(|2x_1+c_1|,|2y_1+c_1|)\) です。操作 \(2\) に対しても同様に考えることで、求める値は整数 \(c_1,c_2\ (\in \lbrace 0,1\rbrace)\) が固定された際に

• \((2x_1+c_1)A+(2x_2+c_2)B=X\)
• \((2y_1+c_1)B+(2y_2+c_2)A=Y\)

を満たす整数の組 \((x_1,y_1,x_2,y_2)\) に対する

\[\max(|2x_1+c_1|,|2y_1+c_1|)+\max(|2x_2+c_2|,|2y_2+c_2|)\]

の最小値となります。

さらに、拡張ユークリッドの互除法を用いることでこの問題は入力から定まる整数 \(e_1,e_2,e_3,e_4\) に対して整数 \(n,m\) に対する

\[f(n,m)=\max(|2Bn+e_1|,|2Am+e_2|)+\max(|2An+e_3|,|2Bm+e_4|)\]

の最小値を求める問題に帰着することができます。以降はこの関数の最小値を求めることを考えます。

この関数の引数を一旦実数に拡張して \(f(x,y)=\max(|2Bx+e_1|,|2Ay+e_2|)+\max(|2Ax+e_3|,|2By+e_4|)\) とします。

この関数の最小値を取る点 \((x_0,y_0)\) は以下の \(2\) つの式から得られる \(4\) つの直線の条件のうち \(2\) つ以上を満たします：

• \(|2Bx+e_1|=|2Ay+e_2|\)
• \(|2Ax+e_3|=|2By+e_4|\)

証明：

\(4\) つの直線の条件のうち \(1\) つ以下しか満たさないと仮定します。

\(f\) は凸関数なので、\((x_0,y_0)\) が最小値を取ることは \(f\) の劣微分 \(\partial f\) に対して \(0 \in \partial f(x_0,y_0)\) が成り立つことと同値です。

\(f_1(x,y)=\max(|2Bx+e_1|,|2Ay+e_2|),\ f_2(x,y)=\max(|2Ax+e_3|,|2By+e_4|)\) とします。

\(f_1\) について、\(|2Bx+e_1|>|2Ay+e_2|\) なら \(\partial f_1=\lbrace (\pm 2B,0)\rbrace\) 、\(|2Bx+e_1|<|2Ay+e_2|\) なら \(\partial f_2=\lbrace (0,\pm 2A)\rbrace\) となります。さらに、\(|2Bx+e_1|=|2Ay+e_2|\) なら \(4\) つの直線の条件のうち少なくとも \(1\) つを満たします（この状態のことを「折れ目に乗る」と表現します）。\(f_2\) についても同様です。

このことを用いると、 \(4\) つの直線の条件のうち \(1\) つ以下しか満たさないという仮定の元では以下の \(2\) 通りしかあり得ません：

• \(f_1,f_2\) 両方折れ目に乗っていない。
• \(f_1,f_2\) 片方だけ折れ目に乗っている。

どちらの状況でも矛盾が発生することを示します。

① \(f_1,f_2\) 両方折れ目に乗っていない場合

\(\partial f=\partial f_1 + \partial f_2 \subset \lbrace (0,\pm 2A),(\pm 2B,0)\rbrace+\lbrace (0,\pm 2B),(\pm 2A,0)\rbrace \not\ni (0,0)\) より矛盾します。

② \(f_1,f_2\) 片方だけ折れ目に乗っている場合

対称性より \(f_1\) だけ折れ目に乗っている場合を考えます。

もし \(|2Bx+e_1|=|2Ay+e_2|=0\) なら \(4\) つの直線の条件のうち既に \(2\) つ満たしているので、\(|2Bx+e_1|=|2Ay+e_2|>0\) の場合を考えます。

このとき、\(\partial f_1\) は \((\pm 2B,0)\) と \((0,\pm 2A)\) を結ぶ線分となります。

一方、\(\partial f_2\) は①の場合と同様に \(\lbrace (0,\pm 2B),(\pm 2A,0)\rbrace\) です。

これらの座標の足し合わせにより \((0,0)\) を作ることはできないので、こちらの場合も矛盾します。

以上より、\(4\) つの直線の条件のうち \(1\) つ以下しか満たさないという仮定の元では必ず矛盾が生じるので題意が従います。

これらを全探索することで \((x_0,y_0)\) を \(O(1)\) 時間で求めることができます。

実は、\(f\) の定義域を整数に限定したときに最小値を取る点 \((n_0,m_0)\) であって、 \(\max(|n_0-x_0|,|m_0-y_0|) \le \color{red}2\color{black}\) を満たすものが存在することが証明できます。

証明：

まず、実数 \(K\geq \min f\) に対し \(f(x,y)=K\) は \(f\) の凸性と affine 性により凸多角形となります。また、この凸多角形の線分の傾きは \(0,\infty, -1,1\) からなります。

このことは \(\max(|x|,|y|)=\max(x,-x,y,-y)\) から関数を分解して場合分けすると分かります。

この事実を用いると背理法で簡単に示すことができます。

この事実により最小値を取る点が高々 \(25\) 個に絞れるので、それらを全探索することで解を求めることができます。（さらに strict に解析することで \(8\) 個の点に絞ることもできます）

以上を適切に実装することでこの問題に正答することができます。計算量はテストケース毎に \(O(\log (A+B))\) です。