一、题目概述

本题给定一个正整数 $n$，需要构造两个整数 $x, y$满足以下条件：

• $\gcd(x, y) = n$
• $x \neq y$
• $1 \le x, y < 2^{63}$

在满足上述约束的前提下，使得 $x \oplus y$（按位异或）的值尽可能小。

题目保证在任意合法的 $n$ 下，始终存在满足条件的解；若存在多种可行方案，输出任意一组即可。

从数据范围上看：

• 测试组数 $T \le 10^4$
• $n < 2^{31}$
• 构造出的 $x, y$ 允许达到 $2^{63}$ 量级

二、问题分析

观察可发现，对于任何gcd(x,y) = n，要使得满足约束条件，必须存在$x \oplus y$= n。因此我们可以令x为n的倍数，则y = x + n。又$x \oplus y$ = n ，所以可以得到 y = x⊕n。将上述两个关于y的式子展开可以得到：

y = x + n = (x ^n ) + (x & n)<<1

y = x + n = y + (x&n) << 1

因此我们可以得到(x & n )<<1= 0。这就可以转换为求满足条件的x值了。由于x是n的倍数，又有x&n=0，所以我们可以推出x = n << 32。这实际上实现了一个位移操作，使得x=n*x^32,又满足x的每一个位置按位与n的值为0。

三、复杂度分析

这很显然是一个O(n)级别的算法

四、参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;

        long long x = n << 32;
        long long y = x | n;

        cout << x << " " << y << "\n";
    }
    return 0;
}