牛客周赛 Round 86--D题

链接：https://ac.nowcoder.com/acm/contest/104637/D
来源：牛客网

思路：

结论：对于任意的x,y，最多不会超过三次操作
原因：由于当a==b时，a^b==0，所以只需要第一次操作和第二次操作时，都取原先的x和y进行相同的操作（记为c和d，且c==d），那么第三次操作一定可以取c,d，作c^d，结果为0
下面为分类讨论
对于一次操作取到0：x==y（这样x^y=0）或x&y==0
对于二次操作取到0：记 x op y == a （op为某个操作），有 a&y==0 || a^y==0
其余的情况的操作数都为3（原因上面已讲）

代码： 

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define db double
#define ldb long double
#define PII pair<int,int>
#define endl "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N=2e5+200;
double eps=1e-6;

void solve() {
	int x,y;
	cin>>x>>y;
	if(x==y || (x&y)==0) {
		cout<<1<<endl;
		return ;
	}
	int a=(x|y);
	int b=(x&y);
	int c=__gcd(x,y);
	int d=(x^y);
	if((a&x)==0 || (a&y)==0 || (b&x)==0 || (b&y)==0 || (c&x)==0 || (c&y)==0 || (d&x)==0 || (d&y)==0) {
		cout<<2<<endl;
		return ;
	}
	if(a==x || a==y || b==x || b==y || c==x || c==y || d==x || d==y) {
		cout<<2<<endl;
		return ;
	}
	cout<<3<<endl;
	return ;
}


signed main() {
	int T;
	cin>>T;
	while(T--) {
		solve();
	}
	return 0;
}