CF627A Xor Equation
题意：a+b=s,a^b=x(异或)。问有多少有序Z+对(a,b)满足条件。
标程：
1 #include<cstdio> 2 using namespace std; 3 typedef long long ll; 4 ll s,x,cnt,t,fl; 5 int main() 6 { 7 scanf("%lld%lld",&s,&x); 8 t=(s-x)/2; 9 if ((t&x)||t<0||((s-x)&1)) return puts("0"),0; 10 if (!t) fl=-2;//减掉为0的两组(a,0),(0,b) 11 for (int i=0;i<=40;i++) 12 if (x&(1ll<<i)) cnt++; 13 printf("%lld ",(1ll<<cnt)+fl); 14 return 0; 15 }
题解：数学
由对称差的思路(a|b)-(a&b)=a^b.
得(a+b)-2(a&b)=a^b.先判一波合法性。
a&b=1 a^b=0 1种
a&b=0 a^b=0 1种（以上两种都有一一对应的关系）
a&b=0 a^b=1 2种
a&b=1 a^b=1 被判掉，不存在
所以只用统计a^b中有多少个1，2^个数就是答案。
注意当s==x时，a&b=0，会有a=0或b=0的情况，要减去，因为a，b∈Z+。