Maximum Even Sum

Let the chosen divisor be $k$. After the operation, the numbers become

$a' = ak, \qquad b' = \frac bk,$

so the sum is

$S(k)=ak+\frac bk.$

We need the biggest even value of this over all divisors $k$ of $b$.

First, ignore parity

Write

$d=\frac bk,$

so $b=kd$ and the sum is

$S=ak+d.$

The obvious greedy-looking move is $k=b$, which gives

$S=ab+1.$

And this is not just a guess. For any divisor split $b=kd$,

$ab+1-(ak+d)=akd+1-ak-d=(ak-1)(d-1).$

Since $ak\ge 1$ and $d\ge 1$, this is nonnegative. So $ab+1$ is the absolute maximum possible sum.

If $ab+1$ is even, answer it immediately. This happens when $ab$ is odd, i.e. both $a$ and $b$ are odd.

That gives:

$a \text{ odd},\ b \text{ odd} \Rightarrow ab+1.$

Now handle parity properly

A sum is even iff both terms have the same parity:

$ak \equiv \frac bk \pmod 2.$

Let $d=\frac bk$. Then $k=\frac bd$, and we are choosing a divisor $d$ of $b$ instead. The sum is

$S=a\cdot \frac bd+d.$

Since the first term grows as $d$ gets smaller, the best valid choice wants the smallest possible leftover $d$ that makes the parity work. No need to cosplay as a factorization algorithm here.

Case 1: $a$ is even

Then $ak$ is always even. So we need $d=\frac bk$ to be even too.

If $b$ is odd, every divisor $d$ is odd, so this is impossible.

If $b$ is even, the smallest even divisor we can leave behind is $d=2$. That means

$k=\frac b2,$

and the answer is

$a\cdot \frac b2+2.$

Case 2: $a$ is odd

Then $ak$ has the same parity as $k$.

• If $b$ is odd, then $k$ and $d$ are both odd, so the sum is odd + odd = even. The maximum is the earlier best value $ab+1$.
• If $b$ is even, we cannot use $k=b$, because then $ak$ is even and $d=1$ is odd, giving an odd sum.

For even $b$, to make the sum even with odd $a$, we need $k$ and $d$ to have the same parity. Since $kd=b$ is even, they cannot both be odd, so they must both be even. That means $b$ must be divisible by $4$.

If $b$ is divisible by $4$, again the best leftover is $d=2$, so

$k=\frac b2,$

and the answer is

$a\cdot \frac b2+2.$

If $b\equiv 2\pmod 4$, there is only one factor of $2$ in $b$, so $k$ and $d$ cannot both be even. Impossible.

Final rules

• If $a$ and $b$ are both odd: answer $ab+1$.
• Else if $b$ is even and $\frac b2$ gives an even sum: answer $a\cdot\frac b2+2$.
• Else answer $-1$.

You can implement the second rule directly by computing

$x=a\cdot\frac b2+2$

when $b$ is even, and checking if $x$ is even. If yes, it is optimal; if not, there is no valid answer.

All values fit in 64-bit signed integers because $ab\le 10^{18}$, and the answers are at most about $10^{18}+1$.

Time complexity: $O(1)$ per test case.