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

· · 题解

题意概述

给定正整数 x，要找到最小的正整数 y，使：

x \& y = \gcd(x, y)

提出假设

设 z = x \& (-x)，其中 z 为二进制中最低位的 1 所对应的值。需要满足：

证明过程

首先证明 y = z。

由于 z 为二进制中最低位的 1 所对应的值，所以 z = 2^t（t 是 x 二进制最低位 1 的位置）。

因为 z = 2^t 并且 x 的最低 t 位全部为 0，故 x = z \cdot n，n 是奇数。因为 z 只在第 t 位为 1，并且 x 的第 t 位为 1，其余位经过位与运算之后皆为 0，故 x \& z = z。

然后计算 \gcd(x, z)。由于 z = 2^t 且 n 是奇数，所以 \gcd(x, z) = z。

发现 x \& z = \gcd(x, z)，故条件成立。

其次证明 \forall y < z 不满足条件。

设 y < z，因为 z = 2^t，所以 y < 2^t。

由于 y 的第 t 位是 0，并且高于 t 的位也都是 0。而且 x 的最低 t 位全部为 0，故：

对 \forall i 有 x_i = 0(i < t)，或者 y_i = 0(i \geq t)，所以 x \& y = 0。

因为两个数的最大公因数 \gcd(x, y) \geq 1，又因为 x \& y = 0，所以 x \& y \ne \gcd(x, y)，故 \forall y < z 不满足条件。

因此，最小整数 y 就是 x \& (-x)。

时间复杂度

单次操作为 O(1)。