数论分块小记

之前在 loj 上写题目的时候碰到的一些问题,在这里记录一下解决方法。

  1. \(\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\) ,大于的时候再去用这个方法加速。
  2. \(\sqrt[k]{\dfrac{n}{i}}\)

    这种时候也是 \(O(n^{\frac{1}{k+1}})\),分析方法同上即可。

    求法也是一样的。

  3. \(\sqrt[p]{\dfrac{n}{i^{p}}}\)

    此时的时间复杂度是 \(O(n^{\frac{1-\frac{1}{q}}{p}})\),分析方法以及分界点找法同上。

上一篇:21.11.2 test


下一篇:【优化调度】基于鸟群算法求解车间调度问题Matlab源码