P8302题解

· · 题解

总体思路

  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 最小的素因子。

不妨列举几项看看规律：

注意到为了验证最小素因子是否为 $ 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 时。

  1. 设 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 ，利用通项式归纳即可。

    由此就证明了其正确性。