题解 CF1110C 【Meaningless Operations】

题意 多组询问 一个数a 求出一个 b (1 <= b < a)使得gcd(a xor b,a and b)最大，输出最大值 经过打表可以知道 大多数情况最大值都是 $2^{[log_{2}a]+1} $-1 （[]表示向下取整） 具体原因是因为我们可以找到一个b，在a的二进制最高位及以下全部按位取反 因为此时b比a少一位，所以b 一定小于a 这时候 a xor b就为$2^{[log_{2}a]+1} $-1 ，a and b为 0 则答案就是$2^{[log_{2}a]+1} $-1 而又因为 a xor b , a and b 都是不可能大于 $2^{[log_{2}a]+1} $-1的（不然二进制就多一位了） 所以$2^{[log_{2}a]+1} $-1一定是最大值 看起来挺合理的，但是总是有意外。当a 为 $2^{k} - 1$时，我们无法按照上面的做法找到一个b 不过由于这样的数最多25个，我们可以暴力打表 打表程序 ``` #include<bits/stdc++.h> using namespace std; int n,m; int gcd(int x,int y) { if(y == 0) return x; return gcd(y,x%y); } int f(int x) { int ans = 0; int o = 0; for(int i = 1; i < x; i ++) { if(gcd(x^i,x&i) > ans) o = i; ans = max(ans,gcd(x^i,x&i)); } return ans; } int main() { int x; for(int i = 1; i <= 25; i ++) { int x = (1<<i)-1; cout<<"s["<<x<<"]="<<f(x)<<";\n"; } return 0; } ``` 提交程序 ``` #include<bits/stdc++.h> using namespace std; map<int,int>s; int T,n,m; int main() { cin >> T; s[1] = 0; s[3] = 1; s[7] = 1; s[15] = 5; s[31] = 1; s[63] = 21; s[127] = 1; s[255] = 85; s[511] = 73; s[1023] = 341; ... //剩下是打表，略 while(T --) { int n ; cin >> n; if(s.count(n)) { cout<<s[n]<<"\n"; } else { cout<<(1<<(((int)(log2(n)))+1))-1<<"\n";; } } return 0; } ```