First, if \(g=\gcd(A,B)>1\), then \(X\) and \(Y\) both must be multiples of \(g\). In that case, dividing \(A,B,X\), and \(Y\) with \(g\) does not change the answer. By this reduction, we now assume \(\gcd(A,B)=1\).

Let us call an operation satisfying \(|x-x'|=A\) and \(|y-y'|=B\) operation 1, and \(|x-x'|=B\) and \(|y-y'|=A\) operation 2.

Fix the parities of the number of times executing operations 1 and 2. If operation 1 is performed \(c_1\ (\in \lbrace 0,1\rbrace)\) times modulo \(2\), the contribution of operation 1 to the \(x\) coordinate is \((2x_1+c_1)A\) for some integer \(x_1\), and that of operation 2 to \(y\) is \((2y_1+c_1)B\) for some integer \(y_1\). Moreover, the minimum number of times one need to perform operation 1 to have a delta of \((2x_1+c_1)A\) to the \(x\) coordinate and \((2y_1+c_1)B\) to \(y\) is \(\max(|2x_1+c_1|,|2y_1+c_1|)\). Applying same discussions to operation 2, the sought value is the minimum value of

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

over the integer tuples \((x_1,y_1,x_2,y_2)\)

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

for each fixed pair of integers \(c_1,c_2\ (\in \lbrace 0,1\rbrace)\).

By the extended Euclidean algorithm, the problem is boiled down to finding the minimum value of

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

on integers \(n\) and \(m\), for some integers \(e_1,e_2,e_3,e_4\) determined by the input. We will now consider how to find minimize the function.

Let us temporarily extend the domain of the function: \(f(x,y)=\max(|2Bx+e_1|,|2Ay+e_2|)+\max(|2Ax+e_3|,|2By+e_4|)\).

The point \((x_0,y_0)\) that the function takes on the minimum value satisfies at least two of the conditions determined by the four lines obtained by:

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

Proof:

Suppose that at most one of the four is satisfied.

Since \(f\) is convex, \(f\) is minimum at \((x_0,y_0)\) if and only if its subgradient \(\partial f\) satisfies \(0 \in \partial f(x_0,y_0)\).

Let \(f_1(x,y)=\max(|2Bx+e_1|,|2Ay+e_2|)\) and \(f_2(x,y)=\max(|2Ax+e_3|,|2By+e_4|)\).

For \(f_1\), if \(|2Bx+e_1|>|2Ay+e_2|\), then \(\partial f_1=\lbrace (\pm 2B,0)\rbrace\), and if \(|2Bx+e_1|<|2Ay+e_2|\), then \(\partial f_2=\lbrace (0,\pm 2A)\rbrace\). Moreover, if \(|2Bx+e_1|=|2Ay+e_2|\), then at least one of the conditions of the four lines is satisfied. (Call this situation “on a crease”.) Same applies for \(f_2\).

Under this definition, when at most one of the conditions of the four lines is satisfied, only the following two cases are possible:

• It is neither on a crease of \(f_1\) nor \(f_2\).
• It is on a crease of only one of \(f_1\) or \(f_2\).

We show that both leads to a contradiction.

1. It is neither on a crease of \(f_1\) nor \(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)\), which is a contradiction.

1. It is on a crease of only one of \(f_1\) or \(f_2\)

By symmetry, we only consider the case where it is on a crease of \(f_1\).

If \(|2Bx+e_1|=|2Ay+e_2|=0\), then two of the four conditions are satisfied, so we have \(|2Bx+e_1|=|2Ay+e_2|>0\).

Then \(\partial f_1\) is the segment connecting \((\pm 2B,0)\) and \((0,\pm 2A)\).

Meanwhile, \(\partial f_2\) is \(\lbrace (0,\pm 2B),(\pm 2A,0)\rbrace\), just as case 1.

The sum of any combination from them equals \((0,0)\), so this also leads to a contradiction.

Hence, the assumption that at most one of the conditions of the four lines always lead to a contradiction, which proves what we want.

By enumerating all of them, \((x_0,y_0)\) can be found in \(O(1)\) time.

In fact, one can prove that there exists a point \((n_0,m_0)\) that takes the minimum when the domain of \(f\) is restricted to integers, such that \(\max(|n_0-x_0|,|m_0-y_0|) \le \color{red}2\color{black}\).

Proof:

First, for a real number \(K\geq \min f\), the convexity and affinity of \(f\) guarantees that \(f(x,y)=K\) forms a convex polygon. Moreover, the slope of any edge of this polygon is \(0,\infty, -1,1\).

This is evident by decomposing the function using \(\max(|x|,|y|)=\max(x,-x,y,-y)\).

It is easy to show the proposition by contradiction using the fact.

By this fact, the candidates of the point that can take the minimum value is narrowed down to \(25\) points; exhaustively evaluating it yields the solution. (A stricter analysis further narrows them down to \(8\) points.)

The problem can be solved by appropriately implementing the algorithm above. The complexity is \(O(\log (A+B))\) per test case.