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

kkksc98 · 2026-05-10 18:40:11 · 题解

题目大意

给定正整数 x，求最小的正整数 y，使得 x \operatorname{and} y = \gcd(x, y)。

题目解法

设 z 为 x 二进制最低为的 1。

首先，我们知道，对于 x 二进制最低为的 1，一定是 x 的因子。

所以 \gcd(x, z) = z，x \operatorname{and} z = z。

所以满足 x \operatorname{and} y = \gcd(x, y)，即 y = z。

所以答案为 x 二进制最低为的 1。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 1e6 + 5;
int T, x;
inline int lowbit(int x) {
    return x & (-x);
}
signed main() {
    ios :: sync_with_stdio (false);
    cin. tie (0), cout. tie (0);
    cin >> T;
    while (T--) {
        cin >> x;
        cout << lowbit(x) << '\n';
    }
    return 0;
}

如果你认为我的题解还行，点个赞并关注我再走吧。