题目题意

给你一个数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();
    }
}