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

Sunrise_up · 2026-05-10 19:14:15 · 题解

求点赞 qwq！

思路

题面看起来可怕，实际上问的问题很简单：给定 x，求最小的正整数 y，满足 (x\ \mathrm{and}\ y)=\gcd(x,y)。

解法一

我们要最小正整数 y，最小的正整数满足条件的，一定是 x 二进制下最低位的 1，即 y_{\min}=\mathrm{lowbit}(x)。

解法二

观察样例，发现答案都是 2^k。

我们直接枚举 y=2^k 即可，范围是 0\le k\le 60，因为 1\le x<2^{60}。

代码

开 long long。

:::success[解法一]{open}

更推荐。

时间复杂度 O(T)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,x;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>T;
    while(T--)cin>>x,cout<<(x&-x)<<'\n';
} 

::: :::success[解法二]

时间复杂度 O(T)，常数大。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,x;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>T;
    while(T--){
        cin>>x;
        for(int i=0;i<61;i++){
            int y=powl(2,i);
            if((x&y)==__gcd(x,y)){
                cout<<y<<'\n';
                break;
            }
        }
    }
} 

:::