偶数段批量处理：当 $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$ 。

P3516.第1题-小美的神秘运算2

1000ms

Difficulty: 3

所属公司 : 美团

算法与标签>模拟

题目内容

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

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

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

小美想知道，在操作 $k$ 次后， $n$ 会变成多少。

输入一行两个整数 $n,k,(2≤n≤10^{18},0≤k≤10^{18})$

输出 $n$ 操作 $k$ 次后的结果。

输入

100 10

输出

说明

输入

100000 100000

输出

输入

预期输出（选填）