ABC238-D AND-and-SUM

問題

提出コード

(テンプレート部分は、省略)

void yesno(bool flag, string yes = "Yes", string no = "No")
{
    if (flag) {
        cout << yes << endl;
    } else {
        cout << no << endl;
    }
}

int main(){
    int T;
    cin >> T;
 
    rep(_, T)
    {
        ll a, s;
        cin >> a >> s;
 
        yesno(a <= s && (a & (s - a)) == a);
    }
}

考えたこと

入力例1.の１つ目
確かに$(x,y)=(3,5)$は$x$ AND $y=1, x+y=8$で条件を満たすけど、$(x,y)=(1,7)$でもOKじゃん
→ $3=11_{(2)}$の先頭の1を5=$101_{(2)}$

条件は、

• $x$ AND $y=a \cdots$(1)
• $x+y=s \cdots$(2)

まず、(2)より、$y=s-x$となるので、(1)は、
$x$ AND $(s-x)=a \cdots$(1)'

ここで、AND演算の結果が$a$になるということは、$x, (s-x)$はそれぞれ下位bitに$a$を持っていることが必要。
（例えば、$a=5=101_{(2)}$なら、$x=????101_{(2)}$, $s-x=???????101_{(2)}$のように表されることが必要。）
嘘でした。

問題は、$?$の部分だが、まず、$2$進数で表したとき、$a$の桁数より大きい部分を上位bitと呼ぶことにする。
例えば、$x=b$が条件を満たす、つまり、
$b$ AND $(s-b)==a$
とする。
このとき、$b$の上位bitの中の$1$を$s-b$の同じ位の方に移し$\cdots$(3)ても、条件を満たす。
[理由]

• まず、$b$と$s-b$の上位bitにおいて、同じ位に1が両方とも立っていることはない。(ANDが$a$にならないので。)
• (3)の操作によっても、$b$と$s-b$の和もANDも変化しない。
  (例)
  入力例1の1つ目、$a=1, s=8$のとき、
  $x=3=11_{(2)}, y=5=101_{(2)}$は条件を満たすが、3の最高位の1を5の方に移してできる、
  $x'=1=1_{(2)}, y'=7=111_{(2)}$もまた、条件を満たす。

よって、結局、(3)の操作を行い続けた結果である、$x=a$のとき、$a$と$s-a$が条件を満たすか否かが答えになるので、
$s-a≥0$のもとで、 $a$ AND $s-a==a$の真偽を答えれば良い。)