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

· · 题解

P16438 [XJTUPC 2026] 共同特征

题目意思找出 x 与一个不超过 x 的数使得他们按位与等于他们最大公约数的最小值。

打暴力的后果

推导公式

设 x 的二进制的 1 第一次出现在 k 位，高位为 A，答案最小取 y=2^{k} 因为再小按位与会等于 0，最大公约数一定大于等于 1 ，所以不成立。 则 y=2^{k}, x=A \times 2^{k+1}+2^{k}，所以 x-1=A \times 2^{k+1}+2^{k}-1，因为 2^{k} 与 2^{k}-1 不同，因此按位与后剩下 A \times 2^{k+1} 再让 x 减去 x 按位与 x-1 得到 2^{k}。也就是等于 y。 所以得到公式 y 等于 x 减去 x-1 与 x 的按位与。

代码

#include<bits/stdc++.h>
using namespace std;
//测试组数
int t;
int main(){
    cin>>t;
    while(t--){
        //int只能存2的31次方数据，用long long
        long long x;
        cin>>x;
        //套公式
        cout<<x-(x&(x-1))<<endl;
    }
    return 0;
}