倍增

概念

倍增是一种为了求解 \(f^n(x)\) ，通过求解 \(f(x), f^2(x),f^4(x), f^{2^m}(x)\) 来求解的方法，直接求解的时间复杂度为 \(O(xn)\)，而使用倍增，就可以达到 \(O(x\log n)\) ，是一种极其方便并且快速的方法。

思路

使用倍增我们需要先证明一下问题：

\(\{x^i|0 \le i < m\}(m \ge 0)\) 可以凑出 \(2 ^ m\) 以内的所有正整数。

\(m = 4\) 时，集合为 \(\{1,2,4,8\}\)，\(2 ^ m = 16\)，此时命题成立。

假设 \(m = k\) 时，命题成立，即 \(A = \{1,2,4,8,\dots 2^{m - 1}\}\) 可以凑出 \(\{x|x < 2^m ,x\in N_+\}\)。

当 \(m = k + 1\) 时，有集合 \(A \in B = \{1,2,4,8,\dots 2^{m - 1}\}\) ， 则一定可以凑出 \(\{x|2^{m - 1},x\in N_+\}\)，同时我们有 \(A\cup B - A\cap B = 2^{m - 1}\) ，那么 \(N = \{x|x < 2^{m - 1},x\in N_+\}\) 一定可以凑成 \(M = \{x + 2^{m - 1}|x < 2^{m - 1} ,x\in N_+\}\)，两者的并集 \(N \cup M = \{x|x < 2^{m},x\in N_+ \}\) 就是 \(2^m\) 以内的所有数。

命题成立。