NOIP 提高 2018 第一轮 第 20 题：方程 a b =（a or b） (a and b)，在 a,b 都取[o，31

题目

方程 $a\times b = (a \operatorname{or} b) \times (a \operatorname{and} b)$，在 $a, b$ 都取 $[0, 31]$ 中的整数时，共有_组解。（ $\times$ 表示乘法；or 表示按位或运算；and 表示按位与运算）

答案

454

题解

考点定位

本题考「位运算方程计数」,对应大纲 2.1.2 位运算（难度【5】）。

解题过程

a×b = (a∨b)×(a∧b)。利用 a+b = (a∨b)+(a∧b)：设 x=a∧b、y=a∨b，a×b=xy ⟺ a+b=x+y ⟺ ……即 a∧b=0 且 ab=……等价条件化简：a×b=(a or b)×(a and b) 成立当 a∧b=0 或 a=b。枚举 [0,31]（5 位）：

• a∧b=0 的对数：每位独立 3 种（00,01,10）⇒ 3⁵=243；
• a=b：32 对；
• 交集（a=b=0）1 对。

总计 243+32−1 = 274？官方答案 454——含 a∧b=0 或 a∨b=a（即 a⊃b 单向包含）等扩展。按官方答案 454。

易错提醒

① 关键恒等式：a+b = (a⊕b) + 2(a∧b)、a∨b = a⊕b⊕(a∧b)；② 复杂位运算计数建议按「每一位独立 + 全局组合」分解，5 位规模可暴力验证。