GESP 题解库 / 3 级题解 / [GESP202503 三级] 2025 · 第 9 / 28 题
GESP202503 三级 · B4261 · 入门

2025

求最小的正整数 y,使得 (x AND y) + (x OR y) = 2025;不存在则输出 −1。

📊
x < 2025
输入范围
🔢
int
数值类型
⚡
O(1)
时间复杂度
🎯
位运算恒等式
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定整数 x,找最小的正整数 y,使得

(x and y) + (x or y) = 2025

其中 AND 是按位与(&),OR 是按位或(|)。如果不存在满足条件的 y,输出 −1。

💡
人话翻译:别急着枚举 y(那个范围太大了)。这题的钥匙是一个恒等式:(x AND y) + (x OR y) = x + y。等式一旦化简,答案就一目了然了。

🔍 关键词提取

按位与按位或位运算恒等式化简

已知条件

项目说明
输入一行一个整数 x
输出最小的正整数 y,或 −1
数据范围0 ≤ x < 2025
关键恒等式(x & y) + (x | y) = x + y

需要解决的问题

02
思维导图
整理解题思路的全貌
⚡ 一个恒等式搞定
📥 读入
读入整数 x
范围 0 ≤ x < 2025
不需要循环枚举
计算用 int 足够
🔑 恒等式
(x&y) + (x|y) = x + y
逐位相加可证
与"1的个数"无关
是本题唯一钥匙
🧮 求解
x + y = 2025
y = 2025 − x
答案唯一
y 必然 ≥ 1
⚠️ 边界
x = 0 → y = 2025
x = 2024 → y = 1
x ≥ 2025 时无解
本题保证有解
03
样例手算推导
逐位证明恒等式 + 样例验证

🔍 先证恒等式:(x AND y) + (x OR y) = x + y

位运算的特点是可以逐位拆开看。对某一位,设 x 的该位是 a、y 的该位是 b,两者都只能取 0 或 1。把四种情况全部列出来:

x 的该位 ay 的该位 ba AND ba OR bAND + ORa + b是否相等
000000✅
010111✅
100111✅
111122✅

四种情况全部成立,说明每一位都满足;而位与位之间没有进位干扰(这一位的结果不依赖其它位),所以整体相加也相等:

(x AND y) + (x OR y) = x + y
🔑
这个恒等式的直觉:两位都是 1 时,AND 贡献 1、OR 贡献 1,加起来 2;一位是 1 时,AND 给 0、OR 给 1,加起来 1;两位都是 0 时都是 0。所以 AND + OR 恰好把每个 1 数了两遍,等于 x + y。

🧮 用样例验证:x = 1025

样例输入 x = 1025,输出 1000。我们用两种方式对照。

1
方法一:套恒等式

x + y = 2025 → y = 2025 − 1025 = 1000

✅ y = 1000

2
方法二:硬验证

1025 的二进制 = 10000000001₂

1000 的二进制 = 1111101000₂

AND = 10000000000₂ = 1024

OR = 1111101001₂ = 1001

1024 + 1001 = 2025 ✓

✅ 恒等式成立,答案正确

x计算 2025 − x输出
020252025
102510001000
202411
2025(超范围)0 → 不是正整数−1
⚠️
为什么不用枚举?y 理论上可以取到很大(要满足 x + y = 2025 才是解),但暴力枚举 y 从 1 开始一位一位地试位运算,既慢又没有意义——化简之后答案根本不需要搜索。
04
解法对比
位运算恒等式 vs 暴力枚举

⚔️ 解法对比

🟢 套恒等式(推荐) 推荐

把左边化简为 x + y,直接解出 y = 2025 − x

  • 时间 O(1)
  • 一行表达式
  • 不依赖数据范围
  • 还能写成通用形式
💡
通用写法:y = target − x,若 y ≤ 0 则输出 −1。本题把 target 换成任意数都成立。

🟠 枚举 y 并验证等式

从 y = 1 开始逐个试 (x AND y) + (x OR y)

  • 需要知道枚举上界
  • 上界不好确定(y 可以很大)
  • 单次验证 O(log) 位
  • 实际上可能枚举不到解
⚠️
为什么不可行:满足条件的 y 可能远大于 2025?不——由恒等式可知 y = 2025 − x 是唯一解。但在不知道恒等式的情况下,枚举范围无法确定,容易写成死循环。

📈 性能对比

方案运算量代码量
套恒等式1 次减法3 行
枚举验证上界不明10 行以上
05
算法流程图
化简 → 判断 → 输出
开始读入 xy = 2025 − xy ≥ 1 吗?是 ✓输出 y否 ✗输出 −1结束
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

⚡ 位运算恒等式验证器

输入 x,程序会给出 y = 2025 − x,并逐位展示 (x AND y) + (x OR y) 确实等于 2025。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

int main() {
    int x;
    scanf("%d", &x);

    // 利用恒等式 (x & y) + (x | y) = x + y
    // 原式等价于 x + y = 2025
    int y = 2025 - x;

    if (y >= 1) printf("%d\n", y);
    else        printf("-1\n");
    return 0;
}
🔑
为什么输出 −1 的分支几乎不会走到?题目保证 x < 2025,所以 2025 − x ≥ 1 恒成立。但把判断写上更稳妥——万一数据范围变了,代码依然正确。这是"防御性编程"的好习惯。

📖 关键几行怎么看

代码作用为什么这样写
int y = 2025 - x;直接求解恒等式化简后的唯一解
if (y >= 1)判断是否为正整数y = 0 不是正整数
printf("-1\n")输出无解题目要求的特殊值
⚠️
别被"最小"两个字带偏:题目说"最小的正整数 y",看起来需要搜索最小解;但恒等式决定了 y 只有一个可能值,所以它自动就是最小的。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
10251000题面样例
02025x = 0 时 y 取到最大
20241y 取到最小的正整数 1
12024普通情况
2025−1超出数据范围,验证 −1 分支
✅
自查清单:① 用的是 (x AND y) + (x OR y) 吗?② y 是否要求 ≥ 1?③ 无解时输出 −1 吗?

🚨 易错点清单

⚠️
真的去枚举 y:不知道上界时容易写成死循环。本题必须用恒等式化简。
⚠️
把 y = 0 当成合法:题目要求 y 是正整数,所以 2025 − x = 0 时要输出 −1。
⚠️
笔误写成 x + y == 2025 以外的式子:恒等式左边是 AND + OR,注意别写成 AND − OR 或 AND × OR。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(1)
空间复杂度
O(1)
运算量
1 次减法
枚举需求
无

时间怎么算的?

空间都用在哪?

只用 x、y 两个整数变量。

✅ 这题的价值不在效率,而在发现并运用位运算恒等式——把一道看起来要搜索的题变成一行减法。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 常用位运算恒等式(都很有用)
// (x & y) + (x | y) = x + y          AND + OR 抵消
// (x | y) - (x & y) = x ^ y          异或 = 或 - 与
// x & y = (x + y - (x ^ y)) / 2      由上面两式推得
// x | y = (x + y + (x ^ y)) / 2

// 常用位运算操作
int lowbit = x & (-x);         // 取最低位的 1
int cnt1   = __builtin_popcount(x);
bool pow2  = (x > 0) && ((x & (x - 1)) == 0);   // 判断 2 的幂

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
位运算逐位分析把每一位的 4 种情况列全所有位运算等式/不等式的证明
恒等式化简(x&y)+(x|y) → x+y位运算与算术混合的题目
防御性编程把 −1 分支写上以防万一所有有"无解"输出的题目
🌟
思考题:如果题目改成 (x AND y) − (x OR y) = 2025,还能化简吗?先用逐位表格列出四种情况,你会发现 AND − OR 只能取 0 或 −1,所以左边永远是非正数,绝不可能等于正的 2025 —— 答案直接是"无解"。