题目回顾

给定两个整数 $a$ 和 $b$，执行一次操作：

1. 选择一个能整除 $b$ 的整数 $k$；
2. 同时执行：$a = a \times k$，$b = b / k$。

求操作后 $a+b$ 的最大偶数值；若无法得到偶数，输出 $-1$。

核心结论（标程思路）

这道题的本质是数学规律 + 贪心： 操作后 $a \times b$ 的乘积永远不变，即：

我们的目标是：在 $x \cdot y = a \cdot b$ 的所有正整数对 $(x,y)$ 中，找到最大的偶数和 $x+y$。

关键数学推导

1. 和的奇偶性规律

• 偶数 + 偶数 = 偶数
• 奇数 + 奇数 = 偶数
• 奇数 + 偶数 = 奇数

要让 $x+y$ 为偶数，必须满足： $x$ 和 $y$ 同奇偶。

2. 最大和的贪心策略

固定乘积 $x \cdot y = S$（$S=a \cdot b$）， $x+y$ 的最大值出现在 一个数尽可能大，另一个尽可能小 时：

• 最大和 = $1 + S$（对应 $x=1,y=S$）
• 次大合法和 = $2 + S/2$（对应 $x=2,y=S/2$，仅当 $S$ 为偶数时合法）

分情况完整解法

设 $S = a \cdot b$。

情况 1：$a$ 和 $b$ 都是奇数

• $S$ 是奇数，只能分解为 奇数 × 奇数；
• 最大合法偶数和 = $1 + S$；

情况 2：$a$ 和 $b$ 一奇一偶

• 只有一种合法偶数方案：$2 + S/2$；
• 前提：$S$ 能被 $2$ 整除（必然满足）；

情况 3：$a$ 和 $b$ 都是偶数

• 本身就满足同奇偶，直接取原和 $a+b$ 就是最大值；

无法得到偶数的唯一情况

• 当且仅当 $a,b$ 一奇一偶，且 $b$ 是奇数（无法选合法 $k$）；
• 此时输出 $-1$。

标程逻辑（C++ 标准代码）

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        ll a, b;
        cin >> a >> b;
        ll ans = -1;
        ll s = a * b;
        
        // 原 a+b 已经是偶数，直接最优
        if ((a + b) % 2 == 0) {
            ans = a + b;
        }
        
        // 两个都是奇数：最大和 1+s
        if (a % 2 == 1 && b % 2 == 1) {
            ans = max(ans, 1 + s);
        }
        // 一奇一偶：合法最大和 2 + s/2
        else if (b % 2 == 0) {
            ans = max(ans, 2 + s / 2);
        }
        
        cout << ans << '\n';
    }
    return 0;
}

样例验证

样例 2：$1\ 8$

• $a=1, b=8$，一奇一偶
• $s=8$
• 答案 = $2 + 8/2 = 6$ ✔️

样例 3：$7\ 7$

• 都是奇数
• 答案 = $1 + 49 = 50$ ✔️

样例 7：$4\ 6$

• 都是偶数，原和 $10$ 不是最优
• 合法最大和 = $2 + 24/2 = 14$ ✔️

总结

1. 操作不改变乘积 $a \cdot b$；
2. 目标：找同奇偶的 $(x,y)$ 使 $x+y$ 最大；
3. 贪心取最大合法值：
   • 全奇 → $1 + a \cdot b$
   • 全偶 → $a+b$
   • 一奇一偶 → $2 + (a \cdot b)/2$
4. 唯一无解：一奇一偶且 $b$ 为奇数 → 输出 $-1$。