思路

• 偶数段批量处理：当 $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}$ 的约束。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned long long n;
    unsigned long long k;
    if (!(cin >> n >> k)) return 0;

    while (k > 0 && n != 1ull) {
        if ((n & 1ull) == 0ull) {
            // 偶数：批量除以2
            unsigned long long tz = __builtin_ctzll(n); // 末尾0的个数
            unsigned long long t = (k < tz ? k : tz);
            n >>= t;
            k -= t;
        } else {
            // 奇数：执行一次 3n+1
            __uint128_t tmp = ( (__uint128_t)3 * n ) + 1;
            n = (unsigned long long)tmp; // 在题目范围内不会溢出
            --k;
        }
    }

    if (k > 0 && n == 1ull) {
        // 进入 1->4->2->1 循环
        unsigned long long r = k % 3ull;
        if (r == 0ull) n = 1ull;
        else if (r == 1ull) n = 4ull;
        else n = 2ull;
    }

    cout << n << "\n";
    return 0;
}

Python

import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    k = int(data[1])

    # Python int 自动大数，不会溢出
    while k > 0 and n != 1:
        if (n & 1) == 0:
            # 偶数：批量除以2
            tz = (n & -n).bit_length() - 1  # 等价于 ctz(n)
            t = min(k, tz)
            n >>= t
            k -= t
        else:
            # 奇数：一次 3n+1
            n = 3 * n + 1
            k -= 1

    if k > 0 and n == 1:
        # 1->4->2->1 循环
        r = k % 3
        if r == 0:
            n = 1
        elif r == 1:
            n = 4
        else:
            n = 2

    print(n)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());

        while (k > 0 && n != 1L) {
            if ((n & 1L) == 0L) {
                // 偶数：批量除以2
                int tz = Long.numberOfTrailingZeros(n);
                long t = Math.min(k, (long) tz);
                n >>= t;
                k -= t;
            } else {
                // 奇数：一次 3n+1（在题目范围内 long 不会溢出）
                n = 3L * n + 1L;
                k -= 1;
            }
        }

        if (k > 0 && n == 1L) {
            long r = k % 3L;
            if (r == 0L) n = 1L;
            else if (r == 1L) n = 4L;
            else n = 2L;
        }

        System.out.println(n);
    }
}

题目内容

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

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

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

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

输入描述

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

输出描述

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

输入

100 10

输出

22

说明

样例2

输入

100000 100000

输出

2