题解：P12336 第三心脏

· · 题解

验题人题解。

当 a 是偶数时，令 a=a'\times2^k(a' \bmod 2 \equiv 1)，用 a' 构造出 b',c',d'，显然 a,b' \times 2^k,c' \times 2^k, d' \times 2^k 是合法的解，所以我们只考虑 a \bmod 2 \equiv 1 即可。

下面默认 a \bmod 2 \equiv 1。

考虑一下 b,c,d 的奇偶性，因为 a 是奇数，所以 b,c,d 要么全偶，要么全奇。

不妨假设 b,c,d 均为偶数，则令 a=2A+1,b=2B,c=2C,d=2D。

条件还是太少了，观察右边的式子，发现 a \oplus b \oplus c 等于常数会好很多，于是我们钦定不妨令 a \oplus b \oplus c = 1，这样我们可以拿到 C=A \oplus B。

把题目里的式子化一下：(2A+1)^2+4B^2+4C^2+4D^2=(2D+1)^2 \to A^2+A+B^2+C^2=D。

那么只需要让 A,B,C 满足 A<B<C 即可，D 显然比 A,B,C 都大，发现此时 \operatorname{highbit}(B)=\operatorname{highbit}(C)>\operatorname{highbit}(A)，随便构一构即可。

一种可能的方法是：令 B=2A,C=A \oplus B，若 B>C 则交换。

但是发现 a=1 时 A=0，则不能直接构造，判一下跑个暴力即可。

于是此题就做完了。