公式解説冒頭の議論により \(\gcd(A,B)=1\) とでき、

\[\begin{cases} Ax_1+Bx_2=X,\\ By_1+Ay_2=Y,\\ x_1\equiv y_1\pmod 2,\\ x_2\equiv y_2\pmod 2 \end{cases}\]

のもと \(\max(|x_1|, |y_1|)+\max(|x_2|,|y_2|)\) を最小化すればよいです。符号や偶奇に関して \(2^6\) 通りの全探索を行うことで、条件は

\[\begin{cases} A_1x_1+Bx_2=x,\\ By_1+A_2y_2=y,\\ x_1,x_2,y_1,y_2\ge 0 \end{cases}\]

となり、目的関数は \(\max(x_1,y_1)+\max(x_2,y_2)\) に書き換えられます。ここで \(|A_1|=|A_2|=A\) です。

\(A_1x_1+Bx_2=x\) より、法を \(B\) としたときの \(A_1\) の乗法逆元 \(A_1^{-1}\) とパラメータ \(s\) を用いて

\[x_1=(xA_1^{-1}\bmod B)+Bs\]

と書けます。代入すれば \(x_2\) もパラメータ \(s\) を用いて書けます。\(y_2, y_1\) に関しても同様の操作をすることで、定数 \(a,b,c,d\) と二つのパラメータ \(s,t\) を用いて

\[\begin{cases} x_1=a+Bs,\\ x_2=b-A_1s,\\ y_1=c-A_2t,\\ y_2=d+Bt \end{cases}\]

と書けました。これを目的関数に代入して展開し、

\[\begin{aligned} x_1+x_2&=a+b+(B-A_1)s,\\ x_1+y_2&=a+c+B(s+t),\\ y_1+x_2&=b+c-A_1s-A_2t,\\ y_1+y_2&=c+d+(B-A_2)t \end{aligned}\]

の最大値を最小化します。\(A_1=A_2\) ならこれらはすべて \(s,t,s+t\) いずれか一つに関する一次式なので、答えを二分探索したとき判定が \(O(1)\) で行えます。

\(A_1\ne A_2\) のとき、一般性を失わず \((A_1,A_2)=(A,-A)\) とすると、

\[\begin{cases} y_1=c+At,\\ y_2=d+Bt \end{cases}\]

はどちらも \(t\) が大きくなるにつれ値が増加するため、\(y_1,y_2\ge 0\) を満たす最小の \(t\) を選ぶとしてよいです。これにより目的関数が \(s\) のみの式になり、やはり二分探索で解けるようになりました。

実装上は、パラメータをどんな値にしても負になる変数が存在する場合を枝刈りし、また \((A_1,A_2)=(-A,-A)\) のとき二分探索せず \(O(1)\) で答えを求めることで高速になります。

実装 (C++, 941ms)