ABC238D - AND and SUM

考え方

桁ごとに考えて，繰り上がりのない$(0,1), (1,0)$の桁と，繰り上がりのある$(1,1)$の桁に分ければ，次の式が成り立つ：

\begin{aligned}
x + y
= \underbrace{(x \mathrm{\,XOR\,} y)}_{\text{繰り上がりなし}}
+ \underbrace{2 \times (x \mathrm{\,AND\,} y)}_{\text{繰り上がり}}
\end{aligned}

アライグマ「D問題はABC172F『Unfair Nim』と同じように、XORとANDの連立方程式に分解して解けるのだ！」https://t.co/3xMYVPlyj2

— 競技プログラミングをするフレンズ (@kyopro_friends) February 5, 2022

したがって，

\begin{aligned}
&
\begin{cases}
\, x \mathrm{\,AND\,} y = a \\
\, x \mathrm{\,XOR\,} y + 2 \times (x \mathrm{\,AND\,} y) = s
\end{cases} \\
&\Leftrightarrow
\begin{cases}
\, x \mathrm{\,AND\,} y = a \\
\, x \mathrm{\,XOR\,} y = s - 2a
\end{cases}
\end{aligned}

となる．これは，bitの各桁ごとの連立方程式と見れば，桁ごとに解くことができる．

つまり，$i$桁目を$(\cdot)_{i}$で表すときに，次が成り立つ．

		$ (x \mathrm{\,XOR\,} y)_{i}$
		0	1
$(x \mathrm{\,AND\,} y)_{i}$	0	$(x_{i}, y_{i}) = (0,0)$	$(x_{i}, y_{i}) = (0,1), (1,0)$
	1	$(x_{i}, y_{i}) = (1,1)$	解なし

以上より，2条件

1. $s - 2a \geq 0$
2. $(x \mathrm{\,AND\,} y) \mathrm{\,AND\,} (x \mathrm{\,XOR\,} y) = 0$（ $a \mathrm{\,AND\,} (s - 2a) = 0$）

が，解が存在するための必要十分条件となる．

回答例

T = int(input())
for _ in range(T):
  a, s = map(int, input().split())
  flag = (s - 2 * a >= 0) and (a & (s - 2 * a) == 0)
  print('Yes' if flag else 'No')