题解

思路

若 $X<N$，等式会变成 $X\mathbin{\mathrm{XOR}}N=X$，不可能成立。

做法

逐位比较可得 $X\mathbin{\mathrm{XOR}}N\ge X-N$；把 $X$ 写成商和余数后可推出商至多为 $1$，故相容数一定满足 $N\le X<2N$。此时余数是 $X-N$，而异或与减法相等当且仅当 $X$ 在 $N$ 的每个为 $1$ 的二进制位上也为 $1$。因此，相容数正是区间 $[N,2N)$ 内所有包含 $N$ 的全部置位的整数。

忽略上界时，这些整数从小到大的顺序恰好对应：把 $K-1$ 的二进制位从低到高依次填入 $N$ 从低到高的零位，再与 $N$ 合并。这样构造出的 $X$ 就是满足置位包含关系的第 $K$ 小整数；最后检查 $X<2N$，不满足则说明相容数不足 $K$ 个，输出 $-1$。

复杂度

每组询问时间复杂度为 $O(\log N+\log K)$，额外空间复杂度为 $O(1)$，构造过程使用 64 位整数。