P9496题解

初墨smik · 2023-08-09 11:31:07 · 题解

题目简述

有 T 组测试数据，每组测试数据给出两个数 n 和 m ,可以对 n 进行按位与或按位或的操作，问多少次操作能让 n 变成 m。

解题思路

这道题每个测试数据可以分为三种情况。

• n=m
• (n\operatorname{and}m)=n$ 或者 $(n\operatorname{and}m)=m
• 另外情况

第一种情况不用解释，n 已经等于 m，题目目的达到，故输出 0。

第二种情况可以举个例子。比如 10 和 2，它们的二进制分别为 1010 和 10，将它们的二进制进行按位与结果等于 1010，这种情况下我们不难发现其中的一个数的二进制是另一个数二进制的后缀，那么此时我们只需要将 n 按位与上 m 就可以了，输出为 1。

第三种情况可以用一种通用方法：将 n 按位与上 0 ，然后再按位或上 m，这样就可以将 n 变成 m，输出为 2。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long int t;
int main(){
    scanf("%lld",&t);
    for(int i = 1;i<=t;i++){
        long long int a,b;
        scanf("%lld%lld",&a,&b);
        if(a == b)printf("0\n");
        else if((a&b) == a || (a&b) == b)printf("1\n");
        else printf("2\n");
    }
    return 0;
}