题解：P16438 [XJTUPC 2026] 共同特征
Forgetlonglong
·
·
题解
这题还是挺水的，除了证明有点烦其他都还好。
数学推导，证明
我们令 g=\gcd(x,y)，则可得 g\mid x,\ g\mid y，令 x=g\times a,\ y=g\times b，满足 \gcd(a,b)=1。
原式条件 x\ \text{and}\ y=\gcd(x,y)，代入可得
只有当 $g$ 是 $2$ 的幂时，按位与才能提取公因数，两边除以 $g$：
$a\ \text{and}\ b=1$。
要使 $y=g\timesb$ 最小：
1. 取 $b=1$，此时 $a\ \text{and}\ 1=1$ 恒成立；
2. $g$ 取 $x$ 最小的正因数，也就是二进制最低位的 $1$，即为 $x$ 与 $-x$ 执行按位与的结果。
因此可以得到最小正整数解 $y_{\min}$，即 $x$ 与 $-x$ 执行按位与的结果。
## 代码
```cpp
#include<iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);//快读
int t;
cin>>t;
while(t--){
unsigned long long x;//不开longlong见祖宗，防止大数据溢出
cin>>x;
cout<<(x&-x)<<"\n";//输出，切记换行
}
return 0;
}
```
管理大大求过！