自动搬运

查看原文

来自洛谷，原作者为

	hfjqwq **

搬运于2025-08-24 22:48:54，当前版本为作者最后更新于2023-08-05 19:07:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感谢

题目大意：

给出两个数 $n$ 和 $m$，$n$ 可以通过按位或或者按位与操作变成 $m$，问最少多少次操作可以实现？

解题思路：

• $n$ 和 $m$ 的二进制当中，如果两个数相同，则不用操作就直接得到，输出 $0$。

• 我们可以知道，通过一次按位与上一个 $0$ 可以使任意一位变成 $0$；按位或上一个 $1$ 可以使任意一位变成 $1$。因此转化思维：我们一次可以将二进制下的 $n$ 任意几位变成 $1$ 或者变成 $0$，问有最少有多少次操作可以变成二进制下的 $m$？ 显而易见答案不是 $1$ 次就是 $2$ 次。分三种情况讨论。

1. 如果存在 $n$ 的某些位上是 $0$，而 $m$ 对应的那一位是 $1$；且不存在 $n$ 的某些位上是 $1$，而 $m$ 对应的那一位是 $0$。就可以通过把这些 $0$ 改成 $1$ 变成 $m$，输出 $1$。

2. 如果存在 $n$ 的某些位上是 $1$，而 $m$ 对应的那一位是 $0$；且不存在 $n$ 的某些位上是 $0$，而 $m$ 对应的那一位是 $1$。就可以通过把这些 $1$ 改成 $0$ 变成 $m$，输出 $1$。

3. 如果同时存在 $n$ 的某些位上是 $0$，而 $m$ 对应的那一位是 $1$，且 $n$ 的某些位上是 $1$，而 $m$ 对应的那一位是 $0$。可以通过两次操作将相应的 $0$ 变成 $1$，相应的 $1$ 变成 $0$，输出 $2$。

解题细节：

注意到数据范围：$n,m \leq 10^{18}$，所以 $n$ 和 $m$ 要开 long long。

CODE:

#include<bits/stdc++.h>
using namespace std;
int T;
long long n,m;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%lld%lld",&n,&m);
		if(n==m){
			printf("0\n");
			continue;
		}
		if((n|m)==n||(n|m)==m){
			printf("1\n");
		}else{
			printf("2\n");
		}
	}
	return 0;
}