牛客周赛 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;
}