思路

• 偶数段批量处理：当 $n$ 为偶数时，可一次性将连续的除以 $2$ 合并。设 $t = \min(\mathrm{ctz}(n),\, k)$（$\mathrm{ctz}$ 为二进制末尾 $0$ 的个数），执行 $n \leftarrow \frac{n}{2^{t}}$，并令 $k \leftarrow k - t$。

• 奇数步单次推进：当 $n$ 为奇数时，执行一次 $n \leftarrow 3n + 1$，并令 $k \leftarrow k - 1$。

• 进入循环后快速跳过：一旦 $n = 1$，序列进入循环 $1 \to 4 \to 2 \to 1$。剩余步数 $r = k \bmod 3$：

  • 若 $r = 0$，则 $n = 1$；
  • 若 $r = 1$，则 $n = 4$；
  • 若 $r = 2$，则 $n = 2$。

• 正确性与复杂度：每次奇数步后必有偶数段，批量除以 $2$ 将长偶数链压缩为 $O(1)$ 次操作；总复杂度与奇数步次数与 $\log n$ 级别相关，远小于 $k$，满足最大 $10^{18}$ 的约束。

题目内容

小美有一个数字 $n$ ，小美打算按照以下规则对 $n$ 进行操作：

如果 $n$ 是偶数，让 $n$ 除以 $2$ ；

否则，让 $n$ 乘以 $3$ 再加 $1$ 。