SZOJ 141 异或

题目描述

有多少种(a,b)(a,b), 使得a+b=s,a xor b=x

输入格式

$s$

输出格式

输出有多少种可能的(a,b)

样例输入

9 5

样例输出

样例解释

$(2, 7), (3, 6), (6, 3), (7, 2)$

数据规模

对于20%的数据，s,x≤10 s,x≤10

对于100%的数据，2≤s≤10^12 2≤s≤10^12, 0≤x≤10^12 0≤x≤10^12

对于100%的数据，a,b≥1

对于a+b

有a+b=a^b+(a&b)/2

异或运算是不带进位的加法运算，在二进制下&只有1&1返回1，这与进位机制相似

那么，将a&b，对应的位数向右移一位，就是原本两个1的所在位置（1+1进位1往左移）

则有（s-x）>> 1转为2进制的1则表示s+b时二进制下需要进位的所在位置

若s<x或 (s-x)>>1不为整数，或((s-x)>>1)&x 不为0

则无解

接下来对于情况分析（接下来皆为按位枚举）

当a^b==0,则a=b=a&b,对答案贡献为*1

当a^b==1,则a=0 b=1，或a=1 b=0，如果a&b==1（有进位），就是非法的，即我们判的((s-x)>>1)&x，输出0

当a&b==0，对于答案的贡献就是*2

根据乘法原理按位判断异或值计算即可

原题出自 codeforces 627 problem A

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
long long x,s,JJ,LY,ans;
inline void Jimmy(){
    scanf("%lld%lld",&s,&x);
    JJ=(s-x)>>1;
    if(JJ & x | s < x | JJ*2+x!=s){
        printf("0
");
        return;
    }
    while(x){
        if(x&1) LY++;
        x>>=1;
    }
    ans=1ll << LY;
    if(JJ==0) ans-=2;
    printf("%lld",ans);
}
int main(){
    Jimmy();
    return 0;
}

View Code