之前在 loj 上写题目的时候碰到的一些问题，在这里记录一下解决方法。
-
\(\lfloor\dfrac{n}{i^k}\rfloor\)
这种类型的时间复杂度是 \(O(n^{\frac{1}{k+1}})\) 的。
-
当 \(i< n^{\frac{1}{k+1}}\) 的时候，只有 \(O(n^{\frac{1}{k+1}})\) 种取值。
-
当 \(i > n^{\frac{1}{k+1}}\) 的时候，\(\lfloor\frac{n}{i^{k}} \rfloor< n^{1-\frac{k}{k+1}}=n^{\frac{1}{k+1}}\) ，也只有 \(O(n^{\frac{1}{k+1}})\) 种取值。
那么这个 \(k+1\) 是怎么求出来的？
我们设最后取值结果大概是 \(O(n^{w})\) 级别的。
那么有 \(n^{1-kw} = n^{w}\) ，解得 \(w=\frac{1}{k+1}\)。
那么问题就在于如何快速求出所有的取值结果了。
我们设当前已经得到了 \(\lfloor\frac{n}{i^k}\rfloor=p\) ，令值为 \(p+1\) 的分母位置的最大值是 \(j\) 。
\[\begin{aligned} \lfloor\frac{n}{j^k}\rfloor&=p+1\\ n&\geq (p+1)j^k\\ j^k&\leq\frac{n}{(p+1)}\\ j&\leq \sqrt[k]{\frac{n}{p+1}}\\ \end{aligned} \]取最大的满足限制的正整数 \(j\) 即可，由于这里面会带一些精度问题，所以一般都是写一个函数来去一个近似位置，然后再 \(O(1)\) 调整到精确位置上。
小技巧：
- 这个东西的常数还是很大的，所以可以在 \(i\leq n^{\frac{1}{k+1}}\) 的时候每次都 \(-1\) ，大于的时候再去用这个方法加速。
-
-
\(\sqrt[k]{\dfrac{n}{i}}\)
这种时候也是 \(O(n^{\frac{1}{k+1}})\)，分析方法同上即可。
求法也是一样的。
-
\(\sqrt[p]{\dfrac{n}{i^{p}}}\)
此时的时间复杂度是 \(O(n^{\frac{1-\frac{1}{q}}{p}})\)，分析方法以及分界点找法同上。