出题症发作

魔法布袋#

有一个魔法布袋：放入 $x$ 枚金币，取出 $f(x)$ 枚。把取出的 $f(x)$ 枚再放进去，取出的会是 $3x$ 枚。即：

f(f(x)) = 3x

$f$ 严格递增，且 $f(1) = 2$ 。金币只能整数颗。

问题：给定 $n$ ，求 $f(n)$ 。

手算小值#

从 $x = 1$ 开始，一步步推。

$x=1$ ： $f(1) = 2$ （已知），所以 $f(2) = f(f(1)) = 3 \times 1 = 3$ 。
$x=2$ ： $f(2) = 3$ （已得）， $f(3) = f(f(2)) = 3 \times 2 = 6$ 。
$x=3$ ： $f(3) = 6$ （已得）， $f(6) = f(f(3)) = 9$ 。

到这里，已知： $f(1)=2,\; f(2)=3,\; f(3)=6,\; f(6)=9$ 。

$x=4$ ： $f(3)=6 < f(4) < f(6)=9$ （严格递增），而 $f(f(4)) = 12$ 。如果 $f(4)=7$ ，则 $f(7)=12$ ；如果 $f(4)=8$ ，则 $f(8)=12$ 。继续推 $x=5$ ： $f(4) < f(5) < f(6)=9$ ，所以 $f(5)$ 只能是剩下的那个。最终得到 $f(4)=7,\; f(5)=8$ ，进而 $f(7)=12,\; f(8)=15$ 。
$x=6$ ： $f(6)=9$ （已得）， $f(9) = f(f(6)) = 18$ 。

继续这个”填空”过程：

$x$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$f(x)$	2	3	6	7	8	9	12	15	18	19	20	21	22	23	24

轨道分解#

观察上表，把每个 $x$ 和它的 $f(x)$ 连起来看，会发现序列分成一条条”轨道”：

1 \to 2 \to 3 \to 6 \to 9 \to 18 \to 27 \to \cdots

4 \to 7 \to 12 \to 21 \to 36 \to 63 \to \cdots

5 \to 8 \to 15 \to 24 \to 45 \to 72 \to \cdots

每条轨道的起点 $s$ 是不被 $3$ 整除的数，然后交替进行两种操作： $f$ 和乘 $3$ ：

s \xrightarrow{f} f(s) \xrightarrow{\times 3} 3s \xrightarrow{f} f(3s) \xrightarrow{\times 3} 9s \xrightarrow{f} \cdots

这里用到一个关键性质： $f(3^k \cdot x) = 3^k \cdot f(x)$ 。证明只需反复用 $f(f(x)) = 3x$ ：

f(3x) = f(f(f(x))) = 3f(x)

归纳即得。

闭形式#

有了轨道分解， $f(x)$ 的闭形式就清楚了。把 $x$ 写成 $x = 3^k \cdot s$ ，其中 $s$ 不被 $3$ 整除。那么 $f(x) = 3^k \cdot f(s)$ ，问题归结为求 $f(s)$ 。

而 $s$ 所在轨道的结构是固定的：

\dots \to s \to f(s) \to 3s \to \dots

在区间 $[3^k, 3^{k+1})$ 内，轨道交替排列：前面的 $s$ 映射到 $f(s)$ （落在同一区间内，偏移 $+3^k$ ），后面的 $s$ 映射到 $3s$ （跳到下一个区间）。

具体地，令 $k = \lfloor \log_3 x \rfloor$ ：

f(x) = \begin{cases} x + 3^k & \text{if } 3^k \le x < 2 \cdot 3^k \\[6pt] 3x - 3^{k+1} & \text{if } 2 \cdot 3^k \le x < 3^{k+1} \end{cases}

验证： $x=4$ ， $k=1$ ， $3^1 \le 4 < 6$ → $f(4)=4+3=7$ 。 $x=7$ ， $k=1$ ， $6 \le 7 < 9$ → $f(7)=3 \times 7 - 9 = 12$ 。和手算一致。

$O(1)$ 算法#

先除掉 $x$ 中所有 $3$ 的因子，用闭形式算出种子 $s$ 的 $f(s)$ ，再乘回 $3^k$ ：

long long f(long long x) {
    if (x == 1) return 2;
    long long k = 0, s = x;
    while (s % 3 == 0) s /= 3, k++;
    long long fs;
    long long pk = 1;
    for (long long t = s; t >= 3; t /= 3) pk *= 3;
    if (s < 2 * pk)
        fs = s + pk;
    else
        fs = 3 * s - 3 * pk;
    while (k--) fs *= 3;
    return fs;
}

cpp

对 $n \le 10^{12}$ 都能秒出。

出题视角#

这个问题的核心壳子是： $f(f(x)) = kx$ ， $f$ 严格单调。它可以衍生出不同难度：

签到级：直接按题目给出的少量数值模拟输出。

整数版（本题）：金币为整数，需要推导出闭形式或写 $O(n)$ 构造。推导轨道分解和分段线性闭形式是主要工作。

非整数版：如果金币可分割（ $f$ 定义在实数上）， $f(f(x)) = 3x$ 且 $f$ 严格递增的解是 $f(x) = \sqrt{3} \cdot x$ 。不需要轨道分解，一次函数即可。

变体：改变复合次数或放大系数—— $f^{(m)}(x) = kx$ ——会产生不同的轨道结构和分段模式。系数 $k$ 和复合次数 $m$ 决定了闭形式的复杂度。

逆函数：给定 $k$ ，求 $f(x) = k$ 的解 $x$ 。从闭形式反解：

x = \begin{cases} k - 3^m & \text{if } 3^m \le k < 2 \cdot 3^m \\[6pt] \frac{k + 3^{m+1}}{3} & \text{if } 2 \cdot 3^m \le k < 3^{m+1} \end{cases}

其中 $m = \lfloor \log_3 k \rfloor$ 。

参考#

原始灵感来自一道趣味数学题，核心条件是 $f(f(x)) = 3x$ 和 $f$ 严格递增。轨道分解的方法可以推广到一般 $f^{(m)}(x) = kx$ 的情形。