CF 2137C - Maximum Even Sum

Rating: 1100
Tags: brute force, greedy, implementation, math
Solve time: 1m 55s
Verified: no

Solution

Problem Understanding

We are given two integers, $a$ and $b$, and we can pick a positive integer $k$ such that $b$ is divisible by $k$. Then we replace $a$ with $a \cdot k$ and $b$ with $b / k$. The goal is to make the sum $a + b$ as large as possible while ensuring it is even. If no choice of $k$ produces an even sum, we return $-1$.

The input consists of up to $10^4$ test cases. Each $a$ and $b$ can be as large as $10^{18}$, meaning that naive iteration over all divisors of $b$ could be expensive, especially if $b$ has large prime factors. Our solution must therefore avoid explicit enumeration over large ranges and focus on reasoning about the parity of numbers rather than all possible multipliers.

Edge cases arise when $a$ and $b$ have different parity patterns. For instance, if both $a$ and $b$ are odd and $b$ is prime, no $k > 1$ divides $b$, and $a + b$ remains odd. Another subtle case is when one number is even and the other odd, but the even number is minimal; it may not be possible to produce a larger even sum without reducing the even component too much.

Approaches

The brute-force approach is to iterate over all divisors of $b$. For each divisor $k$, we compute $a \cdot k + b / k$ and check if it is even, tracking the maximum. This works in principle because every valid multiplier $k$ is a divisor of $b$, but for large $b$, especially those near $10^{18}$, the number of divisors can approach $10^6$ or more, and multiplying large numbers repeatedly could be inefficient. This is correct but potentially too slow for $10^4$ test cases with extreme $b$.

The key insight is that we do not need all divisors. The problem only requires parity: we want $a \cdot k + b / k$ to be even. There are only a few scenarios:

If both $a$ and $b$ are even, any $k$ keeps the sum even, and larger $k$ tends to increase $a \cdot k + b / k$.
If $a$ is odd and $b$ is even, we need $b/k$ even to pair with odd $a \cdot k$ and produce an even sum. Removing a single factor of 2 from $b$ often yields the optimal even sum.
If both $a$ and $b$ are odd, $a + b$ is odd and there is no valid $k$, giving $-1$.

This reduces the problem to examining the parity and factoring out powers of 2 from $b$, rather than considering all divisors.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(sqrt(b) * t)	O(1)	Too slow for large b
Optimal	O(log b * t)	O(1)	Accepted

Algorithm Walkthrough

For each test case, read integers $a$ and $b$.
If the sum $a + b$ is even without any operations, immediately record $a + b$ as a candidate maximum. This handles the simplest case.
If both $a$ and $b$ are odd, the sum is odd and multiplying $a$ by any odd divisor or dividing $b$ by any odd divisor cannot change the parity. In this case, output $-1$.
If $b$ is even, factor out the largest power of 2, call it $x = \text{largest power of 2 dividing } b$. Let $b' = b / x$. The sum $a \cdot k + b / k$ is even if we choose $k$ such that either $a \cdot k$ or $b/k$ is even.
To maximize the sum while ensuring it is even, we consider two candidate multipliers. One is $k = x$, giving $a \cdot x + b / x$. The other is $k = x / 2$ if $x > 1$, giving $a \cdot (x/2) + 2 * b / x$. Take the maximum of these two candidates.
If no valid even sum can be produced through these operations, output $-1$.

Why it works: Factoring out powers of 2 guarantees that we test all possibilities that could turn the sum even, because the parity of $a \cdot k + b/k$ is controlled entirely by the powers of 2 in $a$ and $b$. Since maximizing the sum is monotone with respect to multiplying the larger number by the largest valid $k$, this approach finds the optimal solution without enumerating all divisors.

Python Solution

import sys
input = sys.stdin.readline

def max_even_sum(a, b):
    if (a + b) % 2 == 0:
        return a + b
    if a % 2 == 1 and b % 2 == 1:
        return -1

    # Ensure b is even for factoring
    if b % 2 == 1:
        a, b = b, a

    # factor out largest power of 2 from b
    x = b
    while x % 2 == 0:
        x //= 2

    # candidate k values
    candidate1 = a * (b // x) + x
    if x > 1:
        candidate2 = a * (b // (2*x)) + 2*x
        return max(candidate1, candidate2)
    return candidate1

t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    print(max_even_sum(a, b))

The solution first checks the trivial parity. It then ensures $b$ is even for factorization, extracts the largest power of 2, and considers at most two candidates to maximize the even sum. We avoid iterating over all divisors, which is crucial for large inputs.

Worked Examples

Example 1: 8 1

Step	a	b	a+b	Operation	Result
Initial	8	1	9	sum odd	try operations
Both numbers not even	-	-	-	check powers of 2	b is odd, a+b odd -> -1

The algorithm correctly outputs $-1$.

Example 2: 1 8

Step	a	b	x	candidate1	candidate2
Initial	1	8	-	-	-
Factor largest power of 2 from b	1	8	1	1*(8/1)+1=9	1*(8/2)+2=6
Max even sum	-	-	-	6	-

The optimal even sum is 6, matching the sample.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log b * t)	Each test case factors powers of 2 from b in O(log b)
Space	O(1)	Only a few variables per test case

With $t \le 10^4$ and $b \le 10^{18}$, log b is at most 60. So 60 * 10^4 = 6*10^5 operations, easily within 2s.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = []
    def print_capture(x):
        output.append(str(x))
    input_func = sys.stdin.readline
    t = int(input_func())
    for _ in range(t):
        a, b = map(int, input_func().split())
        print_capture(max_even_sum(a, b))
    return "\n".join(output)

# provided samples
assert run("7\n8 1\n1 8\n7 7\n2 6\n9 16\n1 6\n4 6\n") == "-1\n6\n50\n8\n74\n-1\n14", "sample 1"

# custom cases
assert run("2\n1 1\n2 2\n") == "-1\n4", "small numbers edge"
assert run("1\n1000000000000000000 2\n") == "1000000000000000002", "large numbers even"
assert run("1\n3 6\n") == "12", "odd a, even b"
assert run("1\n5 9\n") == "-1", "both odd numbers"

| Test input | Expected output |