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