题解：CF2085C Serval and The Formula

简要说明题意：

已知

x,y

，求

k

使得

(x+k)+(y+k) = (x+k) \space \textrm{xor} \space (y+k)

，如果不存在输出

-1

。

题目分析：

众所周知

a+b=2(a \space \textrm{bitand} \space b)+a \space \textrm{xor} \space b

，那么只需要找到

k

满足

(x+k) \space \textrm{bitand} \space (y+k)=0

，就能让条件成立。也就是说，

x+k

和

y+k

的任意二进制位不能同时为1。所以输出

-1

的条件就是

x=y

。

考虑到

k

可以大于

x,y

，那么直接从低位开始扫，两数的某位如果同时为

1

，就把大的那个加进位。这个过程可以迭代，可以解决问题。

代码如下：

CPP

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int T;
    long long x,y,t,temp,cnt,k;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&x,&y),k=0ll,t=(x&y);
        if(x==y){
            printf("-1\n");
            continue;
        }
        while(t){
            temp=(t&(-t)),temp=(temp<<1)-1;
            cnt=min(((x&temp)^temp)+1,((y&temp)^temp)+1);//计算要加到进位差多少，可能有更简单的表达方式？
            k+=cnt,x+=cnt,y+=cnt;
            t=(x&y);
        }
        printf("%lld\n",k);
    }
    return 0;
}
/*
1
3 7
*/

题解：CF2085C Serval and The Formula

文章操作

简要说明题意：

题目分析：

相关推荐

评论

题解：CF2085C Serval and The Formula