CF1271E Common Number

首先，定义函数 $f(x)$ 如下： $$ f(x) = \begin{cases} \frac{x}{2} & \text{如果 } x \text{ 是偶数} \\ x - 1 & \text{否则} \end{cases} $$ 我们可以发现，如果选择某个值 $v$，并不断对其应用函数 $f$，即对 $f(v)$ 再应用 $f$，如此反复，最终一定会得到 $1$。我们将这个过程中得到的所有值按顺序记录在一个列表中，记为 $path(v)$。例如，$path(1) = [1]$，$path(15) = [15, 14, 7, 6, 3, 2, 1]$，$path(32) = [32, 16, 8, 4, 2, 1]$。 现在，对于每个 $x$ 从 $1$ 到 $n$，都写出 $path(x)$。问题是：存在多少个不同的 $x$，使得某个值 $y$ 出现在 $path(x)$ 中？请你求出最大的 $y$，使得 $y$ 至少出现在 $k$ 个不同的 $path(x)$ 中。 形式化地说，你需要找到最大的 $y$，使得 $$ \left| \{ x \mid 1 \le x \le n,\, y \in path(x) \} \right| \ge k $$ 成立。

第一行包含两个整数 $n$ 和 $k$，满足 $1 \le k \le n \le 10^{18}$。

输出唯一的整数——在至少 $k$ 个不同路径中出现的最大值。

在第一个样例中，答案是 $5$，因为 $5$ 出现在 $path(5)$、$path(10)$ 和 $path(11)$ 中。 在第二个样例中，答案是 $4$，因为 $4$ 出现在 $path(4)$、$path(5)$、$path(8)$、$path(9)$、$path(10)$ 和 $path(11)$ 中。 在第三个样例中，$n = k$，所以答案是 $1$，因为 $1$ 是唯一一个在 $1$ 到 $20$ 的所有路径中都出现的数字。 由 ChatGPT 4.1 翻译