概述

本题要求给定整数 ~k~，构造一个不超过 ~10^6~ 的正整数 ~n~，使得经过 ~k~ 次考拉兹函数变换后恰好得到 ~1~。核心解法是利用考拉兹序列在 ~1~ 附近的周期 ~3~，根据 ~k \bmod 3~ 直接输出 ~1~、~2~ 或 ~4~。

分析

核心观察

考拉兹函数在 ~1~ 处的循环为 ~1 \to 4 \to 2 \to 1~，周期为 ~3~。

思路

对于 ~n=1~，有 ~f(1)=4~，~f^2(1)=2~，~f^3(1)=1~。因此：

• 若 ~k \equiv 0 \pmod 3~，则 ~f^k(1)=1~，输出 ~1~。
• 若 ~k \equiv 1 \pmod 3~，则 ~f^k(2)=1~，因为 ~f(2)=1~，之后每 ~3~ 步循环一次，输出 ~2~。
• 若 ~k \equiv 2 \pmod 3~，则 ~f^k(4)=1~，因为 ~f(4)=2~，~f^2(4)=1~，输出 ~4~。

这些输出都满足 ~1 \le n \le 10^6~。

具体示例

样例 ~1~ 中 ~k=9~，~9 \bmod 3 = 0~，输出 ~1~ 满足 ~f^9(1)=1~。样例给出 ~12~，同样满足，因为 ~12~ 到 ~1~ 需要 ~9~ 步，而 ~9 \equiv 0 \pmod 3~，所以 ~f^9(12)=1~。输出任意一个即可。

算法步骤

1. 读取 k。
2. 计算 k 对 ~3~ 取模的余数 r。
3. 若 r 等于 ~0~，输出 ~1~；若 r 等于 ~1~，输出 ~2~；否则输出 ~4~。

复杂度分析

• 时间：~O(1)~
• 空间：~O(1)~

实现注意事项

• k 最大为 ~10^9~，使用 int 或 long long 均可。
• 输出的是整数，不需要浮点数。
• 模运算结果直接用于分支。

源代码

#include <iostream>
using namespace std;

int main() {
    long long k;
    cin >> k;
    int r = k % 3;
    if (r == 0) cout << 1 << endl;
    else if (r == 1) cout << 2 << endl;
    else cout << 4 << endl;
    return 0;
}

k = int(input())
r = k % 3
if r == 0:
    print(1)
elif r == 1:
    print(2)
else:
    print(4)