题目题意:
给你一个数n,n为两个数x、y的最大公约数,问我们是否能找到两个数,使 x⊕y 的值最小。
题目知识点:
位运算、思维
题目分析:
由题目可知,x和y均是n的倍数,那么就可以知道|x-y|>=n的,当且仅当他们仅相差一倍时取等。
又根据按位异或运算的性质得, x⊕y >= |x-y|,既然题目要求 x⊕y 要最小,即 x⊕y = n 。
随之,当我们所给的n左移n本身二进制的位数cnt,即n<<cnt,一定为n的倍数,因为n<<cnt就相当于n·2^cnt,这个时候我们令x=(n<<cnt),那么我们的y就可以为x+n;
比如我们的n=15,那其二进制就为1111,这时cnt=4,那么x的二进制就为11110000,而我们的y的二进制就为11111111,因此 x⊕y 根据"异1同0"的规律得到的值就是最小值n,即为15。
想到这,代码大概就可以写了:
#include<bits/stdc++.h>
using namespace std;
void solve(){
int cnt=0; //用来计n的二进制位数
long long n;
scanf("%lld",&n);
long long t=n;
while(t){
cnt++;
t/=2;
} //统计二进制位数
long long x=0,y=0;
x=(n<<cnt); //将n左移cnt位得到x
y=x+n; //得到y
cout<<x<<" "<<y<<endl;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
solve();
}
}

京公网安备 11010502036488号