自动搬运

查看原文

来自洛谷，原作者为

	DESCENDANTSOFDRAGON A.F.O.

搬运于2025-08-24 22:37:50，当前版本为作者最后更新于2023-07-20 14:43:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

总体思路

1. 若 $3 \mid k$。则令 $m_{0}=-1$。
2. 若 $3 \nmid k$。下面判断 $2$ 是否整除 $n$。
3. 若 $2 \mid n$。若 $V_{2}(n) \geq 2$，则令 $m_{0}=V_{2}(n)-2$ 若 $V_{2}(n) = 1$，则令 $m_{0}=0$。
4. 若 $2 \nmid n$。下面判断 $3$ 是否整除 $n$。
5. 若 $3 \mid n$。则令 $m_{0}=0$。
6. 若 $3 \nmid n$。若 $V_{2}(n+ \frac{n}{p} ) \geq 2$，则令 $m_{0}=V_{2}(n+ \frac{n}{p} )-1$。若 $V_{2}(n+ \frac{n}{p} )=1$，则令 $m_{0}=1$。

证明

首先取 $p$ 是 $n$ 最小的素因子。

不妨列举几项看看规律：

$f_{0}=n$，$f_{1}=n+ \frac{n}{p}$，$f_{2}=n+ \frac{n}{p} + \frac{n+\frac{n}{p}}{2}$，······

注意到为了验证最小素因子是否为 $2$，我们需讨论 $n$ 的奇偶性。

1. 若 $2 \mid n$。

   则每次迭代为：$n$，$n+\frac{n}{2}$，······

   但此时我们不知道 $2$ 能被除多少次。

   设 $V_{2}(n)$ 表示 $n$ 中含 $2$ 的幂次，设 $V_{2}(n)=t$，$n=2^t·l$，$2 \nmid l$

   我们手动迭代一下：$ 2^t·l \to 3·2^{t-1}·l \to 3^2·2^{t-2}·l \to ······ \to 3^i·2^{t-i}·l $

   这时会惊奇的发现，$2$ 的幂次在一步步削减，$3$ 的幂次在一步步上升，最终都可转化为 $3^{n}·l$ 的问题。

   那么研究 $n$ 是奇数，且 $3 \mid n$ 时。

2. 设 $n=3t$。

   我们再次手动迭代：$ 3t \to 4t \to 6t \to 9t \to 12t \to 18t \to ····· $

   注意到似乎 $3^{i}·t$ 型的数总会出现，事实上我们可以归纳证明

   $f^{3i}=3^{i+1}·t$，$f^{3i+1}=4·3^{i}·t$，$f^{3i+2}=6·3^{i}·t$

   再考虑 $k \bmod 3$ 的余数。

   我们证明 $3 \nmid k$ 时 $m_{0}=-1$ ：

   若存在 $m_{0}$，设 $3i+1>m_{0}$

   则 $f^{3i+1}(n)=4·3^i·t$

   由于 $3 \nmid k$，故 $3i+1+k \not\equiv 1 \pmod 3$。

   故 $f^{3i+1+k}(n)$ 是 $f^{3i+2}$ 或 $f^{3i}$ 型。

   故 $V_{2}(f^{3i+1+k}(n)) \leq 1$，与上矛盾。

   而对于 $3 \nmid k$ 时，$m_{0}=0$，利用通项式归纳即可。

   由此就证明了其正确性。