`算法题解` `AcWing` 4617. 解方程

题目链接

题解

给定一个非负数 $A$, 对于所有的 $x\in [0,x]$, 问有多少个 $x$ 满足: $A-x=A^x$

比如 $A=2$, 则有: $2-0=2\otimes 0,2-1\ne 2\otimes 1,2-2=2\otimes 2$

---

对于
$\begin{array}{rl}A& =1010\\ x& =abcd\end{array}$

对于A中的bit位为0的位:
假如 $b或d$ 是1, 那么, 在这个bit上, 其(异或值为1) 而(相减值为0)
两个数在某一位上不同, 则两个数必然不同; 此时一定有: (A - x) != (A ^ x)

还要证明一点: 不像(异或) 是完全位独立的; 减法会涉及到(借位)情况;
所以要证明: 假如A的当前位被借位了, 本来是0, 现在是1; 那么这种情况会是答案吗?
… 此时, 说明: 低位中的某一位x, 发生了: (0 - 1)的情况, 才会导致当前位被借位;
… 那么, 对于x位, 他的(异或值1) != (相减0)
因此, 这种情况不存在; A中的0, 不会被借位 不会变成1.

即: 所有A的bit为0的位, x在该位上 也是0

只需考虑: (a, c)即可;

假如(c = 0), 那么, 该位的异或值为1, 相减值为1 (前提是: 低位不会把A的这个1 给借过去, 下面会证明)
假如(c = 1), 那么, 该位的异或值为0, 相减值为0 (前提是: 低位不会把A的这个1 给借过去, 下面会证明)

证明: A里的1, 在相减时, 一定不会被低位借过去;
… 对于低位中的0, 由于x也对应为0, 因此, 其不会借位;
… 对于低位中的1, 不管对于的x位是(0或1), 都够相减, 不需要向上借位;

综上: x中的(b, d)必须是0, 且(a, c)任意;

令C = A中的1的个数, 则答案为: $2^C$