F 和和和

Description:

• 给定两个非负整数\(a,b\)，判断是否存在两个非负整数\(x,y\)，使得 \(x+y=a\) 且 \(x\&y = b\)。其中，\(\&\)表示二进制的按位与运算。

Constraints:

• \(1 \leq T \leq 10^5\)
• \(0 \leq a,b \leq 10^{18}\)

Analysis:

• 数据量显然不能够枚举模拟，那就从与运算的性质入手。
• 因为 \(x\&y = b\)，考虑 \(b\) 的二进制：
  情况一： \(b\) 的某位是 \(1\)，则说明该位上 \(x,y\) 均为 \(1\) ；
  情况二： \(b\) 的某位是 \(0\)，则说明该位上 \(x,y\) 至多一个 \(1\)
• 考虑 \(x+y\) 最小的情况，则情况二中 \(x,y\) 对应二进制位全为 \(0\)，此时 \(x+y=2b\)
• 剩下的可加的范围即二进制位不全为1，举个栗子，对于 \(b=4=(100)_2\) 则 \(x=y=(1??)\)，考虑最后两位的差值， \(??=(.10),(.01),(.11)\)，其共同特点是差值与 \(b\) 的最后两位 \((.00)\) 的按位与结果为 \(0\) ，故可以调整到的差值 \(a-(x+y)_{min}=a-2b\) 和 \(b\) 与运算的结果必须为 \(0\)

Solution:

#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007

typedef long long ll;
typedef unsigned long long ull;

void solve() {
	ll a,b; cin >> a >> b;
	bool flag;
	if(a < 2*b ) flag = false; // a >= 2b 是必要条件
	else if((a-2*b) & b) flag = false;
	else flag = true; 
	cout << (flag ? "YES" : "NO") << endl; //注意括号
}

int main() {
	int T; cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}