题解

题目解析

• 输入输出：输入一个整数 $x$ ($0 \le x < 2025$)。输出最小的正整数 $y$，使得 (x \bitand y) + (x \bitor y) = 2025；若不存在则输出 $-1$。
• 数据范围：$0 \le x < 2025$。目标值 $2025$ 的二进制位数约为 $11$ 位（$2^{10}=1024, 2^{11}=2048$）。
• 复杂度要求：代码采用枚举策略，时间复杂度 $O(2^{\lceil\log_2 2025\rceil}) \approx O(2025)$，可接受；也可利用数学性质优化至 $O(1)$。
• 算法知识点：位运算性质、枚举、数学推导

思路解析

1. 关键数学性质：对于任意两个整数 $a, b$，存在恒等式 (a \bitand b) + (a \bitor b) = a + b。该性质对二进制下的每一位均成立（$0+0=0\&0+0|0$, $1+0=1\&0+1|0$, $1+1=1\&1+1|1$），故对整体亦成立。
2. 方程化简：原条件 (x \bitand y) + (x \bitor y) = 2025 可转化为 $x + y = 2025$，即 $y = 2025 - x$。
3. 解的存在性：由数据范围 $x < 2025$ 可知 $y = 2025 - x \in [1, 2025]$，故正整数解必然存在且唯一。
4. 枚举策略（代码实现）：代码选择直接枚举验证。计算 $2025$ 的二进制位数 $\textit{bit\_length} \approx 11$，在 $[0, 2^{11}]$（即 $[0, 2048]$）范围内从小到大枚举 $i$。由于 $2025 < 2048$，该范围必然包含正确答案。首个满足位运算等式的 $i$ 即为最小正整数 $y$。
5. 终止条件：若枚举结束未找到（理论上不会发生在此数据范围），输出 $-1$。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 计算2025的二进制位数（2025 < 2^11 = 2048，故为11位）
    int bit_length = log2(2025) + 1;
    int x;
    cin >> x;
    // 枚举可能的y值，上限设为 2^bit_length 确保覆盖2025
    for (int i = 0; i <= pow(2, bit_length); i++) {
        // 关键判断：利用位运算恒等式 (x&y)+(x|y) == x+y 验证是否等于2025
        if ((x & i) + (x | i) == 2025) {
            cout << i << endl;
            return 0;  // 找到最小正整数y，立即退出
        }
    }
    cout << -1 << endl;  // 未找到（在本题数据范围内不会发生）
    return 0;
}