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

123456wjc · 2026-05-10 22:47:11 · 题解

题目简述

给定 x，求一个正整数 y，使得 x \& y = \gcd(x,y)，且 y 最小。

思路简析

经过简单的推导，我们发现按位与的结果需要等于 y，y 还要尽可能小。那我们就想到了 \operatorname{lowbit} 运算，也就是取 x 的最低有效二进制位。由于小于最低有效位的答案按位与为 0，因此这个结论也必然成立。

code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        long long k;
        cin>>k;
        cout<<(k&(-k))<<'\n';
    }
}