题意

找到两个数x,y，使得gcd(x,y)=n,并且x与y的异或运算的值最小。

关键词

构造，数论，位运算

题解

异或运算是两个数的二进制位，如果相同为0，不同则为1，即可看成不进位的加法或者不退位的减法。

故可得出|y-x|<=x^y<=x+y这个不等式。

所以如果想让异或运算的值最小，也就是让他等于|y-x|。那不妨设x<y,又因为gcd(x,y)=n，故x=an,y=bn，且a与b应该互质。故y-x的最小值应该为n。所以我们只要构造x与y让其最大公约数为n，且x^y=n。

观察数据范围，n<2^31,x,y<2^63。他们二进制位数差32，恰好大于n的最大二进制位数，如果y与x 前面位都相等，后面位恰好差n,这样子x^y恰好等于n,所以构造x=2^k*n,y=(2^k+1)n,又因为系数刚好连续，故一定互质，满足gcd(x,y)=n，而k为32，恰好可以一直满足后面位相差n,前面位一样。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        long long n;
        cin>>n;
        long long x=n<<32;
        long long y=(n<<32)+n;
        cout<<x<<" "<<y<<endl;
    }
}