题解：P16438 [XJTUPC 2026] 共同特征

nanjingxuan2011 · 2026-05-11 08:51:50 · 题解

题意

求在满足 \& 给出的数和与给出的数的 \gcd 相等的条件下的最小数。

解法

由于二进制数每位权重倍增，显然一个数是自身 lowbit 的倍数，\gcd 求出的就是 lowbit。而一个数 \& 自身 lowbit 显然是除零之外的最小结果，因 \gcd 出来的不可能是零，可以证明 x 的 lowbit 即本题答案。

小技巧

这道题涉及负数的补码与原数不同和与运算的一些性质。

众所周知，负数的补码等于原数取反后加一。观察以下例子：

原数：101000
补码：011000

可以发现原数 lowbit 后的零取反为一后加上一，会使 lowbit 又变回一。因为其他位都已取反，此时 \& 原数就可以得出 lowbit 进行输出即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
constexpr int maxn=1e5+10;
int t,x;
signed main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&x);
        int s=x&-x;
        printf("%lld\n",s);
    }
    return 0;
}