本来这题想用枚举暴力解的,但是运行总是超时,数值范围太大了~,所以该题不能用枚举进行暴力。
转换成二进制,我们判断一下其规律
注意:按位与是都为1时其值才为1,所以当x和y按位与的结果为2时,其x和y的二进制的第二位一定都为1。所以x,y必定大于等于2。暴力解的话枚举可以从2开始。但是这种方法还是会面临超时的问题。
观察到x和y的和为8,那么这个和已知的贡献是x和y都有的2。因此剩余部分为8-2*2=4这个4转换成二进制为100,因此4的贡献可能是x或y中的某个。x和y按位与结果为010(同1时才为1),符合按位与的结果。
对于案例二,按位与结果是4 和为6,这是不成立的,因为按位与的x和y都贡献出了4,所以x和y的值必然是大于等于4的。
我们再举个反例,比如按位与的结果是2,但是和为10。此时x和y已知贡献为4。剩余部分x和y的共计需要贡献出6,转换成二进制为110,而这个第二位的1必定是其中一方贡献出来的,但是x和y已知的都贡献出了第二位的1(010),因此,这种情况下不能找到对应的x,和y
所以:如果想判断出是否存在这个x和y
1、和-2按位与>=0
2、(和-2按位与)&按位与 ==0.
对应的python代码如下:
import os
import sysn = int(input())
for _ in range(n):a,b = input().split()a = int(a)b = int(b)temp = b-2*aif temp < 0:print("NO")else:flag = Falsewhile temp!=0 and a!=0:if (temp%2==1 and a%2 == 1):print("NO")flag = Truebreaktemp = temp//2a = a//2if flag == False:print("YES")