2025 题解

一、题目分析

题目给定一个整数 ( x )，要求我们找到最小的正整数 ( y )，使得以下等式成立：

[
(x \mathbin{&} y) + (x \mathbin{|} y) = 2025
]

其中 (&) 表示按位与运算，(|) 表示按位或运算。如果不存在这样的正整数 ( y )，则输出 (-1)。

二、解题思路

1. 重要的位运算恒等式

本题的关键在于下面的恒等式：

对于任意整数 ( a, b )，恒有：

[
a + b = (a \mathbin{&} b) + (a \mathbin{|} b)
]

为什么成立？
我们从二进制加法的角度来理解：

• 按位异或 ( a \oplus b ) 表示不考虑进位的加法结果。
• 按位与 ( a \mathbin{&} b ) 表示两位均为 1 的位置，这些位置在加法中会产生进位，且进位会使结果增加 ( 2 \times (a \mathbin{&} b) )。
  因此有：

[
a + b = (a \oplus b) + 2 \times (a \mathbin{&} b)
]

而按位或又可以拆分为：

[
a \mathbin{|} b = (a \oplus b) + (a \mathbin{&} b)
]

将两者相加：

[
(a \mathbin{&} b) + (a \mathbin{|} b) = (a \mathbin{&} b) + (a \oplus b) + (a \mathbin{&} b)
= (a \oplus b) + 2 \times (a \mathbin{&} b) = a + b
]

所以恒等式成立。

2. 转化条件

利用该恒等式，原条件等价于：

[
x + y = 2025
]

也就是说，只需要找到一个正整数 ( y )，使得它与 ( x ) 的和等于 2025 即可。显然：

[
y = 2025 - x
]

由于题目要求 ( y ) 为正整数，所以：

• 如果 ( 2025 - x > 0 )，即 ( x < 2025 )，那么 ( y = 2025 - x ) 就是唯一解，也是最小的正整数解。
• 如果 ( 2025 - x \le 0 )，即 ( x \ge 2025 )，则不存在正整数 ( y ) 能满足条件，应输出 (-1)。

3. 与暴力枚举的关系

参考代码使用了从 1 到 2025 的循环枚举 ( i )，并检查是否满足原始等式。
由于恒等式的存在，第一次遇到的满足条件的 ( i ) 必然就是 ( 2025 - x )，所以暴力枚举也能得到正确结果，只是时间复杂度为 ( O(2025) )。

三、算法说明

在已知恒等式的前提下，解题只需一步：

1. 读入整数 ( x )。
2. 判断：若 ( x < 2025 )，则输出 ( 2025 - x )；否则输出 (-1)。

时间复杂度：( O(1) )。
空间复杂度：( O(1) )。

当然，若采用参考代码的方法，遍历 1 到 2025 也是可行的，因为常量范围极小。

四、代码实现与解释

参考代码（暴力枚举）

cpp
复制
1#include <cstdio>
2using namespace std;
3int x;
4int main() {
5    scanf("%d", &x);
6    for (int i = 1; i <= 2025; i++)   // 在 1~2025 范围内寻找 y
7        if ((x & i) + (x | i) == 2025) { // 检查题目给出的条件
8            printf("%d\n", i);
9            return 0;
10        }
11    printf("-1\n");   // 没有找到则输出 -1
12    return 0;
13}

解释：

• 从 1 开始枚举可能的 ( y )，最多枚举到 2025。
• 对于每个 ( i )，直接计算 (x & i) + (x | i)，如果等于 2025 则输出并结束程序。
• 由于循环是从小到大枚举，第一个找到的 ( i ) 就是最小的正整数解。
• 若循环结束仍未找到，说明不存在解，输出 -1。

优化代码（O(1) 做法）

cpp
复制
1#include <cstdio>
2
3int main() {
4    int x;
5    scanf("%d", &x);
6    int y = 2025 - x;
7    if (y > 0)
8        printf("%d\n", y);
9    else
10        printf("-1\n");
11    return 0;
12}

解释：

• 直接利用恒等式得出 ( y = 2025 - x )。
• 判断 ( y ) 是否为正整数，是则输出，否则输出 -1。

五、时间复杂度分析

• 暴力枚举方法：循环次数最多为 2025 次，每次检查和判断为 ( O(1) )，总复杂度 ( O(1) )（常数范围）。
• 数学直接推导方法：仅进行一次减法和一次比较，复杂度 ( O(1) )。

在实际比赛中，两种方法均可在 1ms 内轻松通过，不过后者更优雅高效。

六、总结

本题考察了对位运算基本性质的理解，特别是恒等式 ( a + b = (a \mathbin{&} b) + (a \mathbin{|} b) )。一旦发现这一规律，题目就由“位运算搜索”转变为“简单四则运算”，大大降低了难度。对于初学者而言，无法立刻看出恒等式时，采用循环暴力枚举也是一种可行的保底策略。