Codeforces 627A XOR Equation（思路）

题目大概说两个正整数a、b，已知s=a+b以及x=a xor b的值，问有几种a、b这样的数对。

我知道异或相当于无进位的加法，s-x就是其各个位置的进位，比如s-x=1010，那就表示a和b的第1位和第3位发生的进位。
这样，对于某些位其值就能确定，对于有些位其值不能确定（该位xor和为1且没有发生进位），这时a和b的该位都能选择0或者1，对于不确定的就是乘法原理答案累乘2。
另外还有一些情况是不可能的，首先s<x不可能，s-x是奇数不可能，某一位xor和是1且发生了进位这不可能。
最后注意是正整数，而出现0只有s=x的情况，这时答案要减去2。

还看了数据才A了这题。。好弱。。

官方的题解清楚多了：s = a+b = a xor b + (a and b)*2。。然后。。比上面清楚多了。。

 #include<cstdio>

 using namespace std;

 int main(){

     long long s,x;

     scanf("%lld%lld",&s,&x);

     long long n=s-x;

     if(x>s || (n&)){

         putchar('');

         return ;

     }

     long long res=;

     for(int i=; i<=; ++i){

         if((x>>i-&) && (n>>i&)==) res<<=;

         if((x>>i-&) && (n>>i&)){

             putchar('');

             return ;

         }

     }

     if(x==s) res-=;

     printf("%lld",res);

     return ;

 }

巴特西

Codeforces 627A XOR Equation（思路）

最新文章

热门文章