寒假算法基础集训营2 F题题解

首先观察样例可以猜出x⊕y最小值为n，下面给出证明。由于异或运算可以看成是不带退位的减法，所以|x−y|<=x⊕y。又由于gcd(x,y)=n，所以x,y可分别看成n* a,n* b,a,b需互质所以，|x−y|=|a-b|*n，a,b互质最小差值为1。所以得证x⊕y最小值为n。

对于如何构造出x,y，我们只需将n看成二进制，将其左移m位，即末尾补m个0，即构造x=n*(2^k),由上段构造y=n*(2^k+1)。y的二进制就是x的m个0处加上一个n的二进制，所以可得想要x⊕y=n，需满足n的二进制位数<=m。由题n<2^31,可知n二进制最多31位，所以k即m取31即可。

附本人ac码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 998244353
const ll N=1e6+10;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    int t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n; 
		cout<<(n<<31)<<" "<<(n<<31)+n<<endl;
	}
	return 0;
}