Dirichlet 双曲线法
Leasier
·
·
算法·理论
你可能以为我想讲 SP26073 DIVCNT1，但事实并非如此。
我们有时需要处理这样一类问题：
- 给定 n，求 \displaystyle\sum_{1 \leq xy \leq n} f(x) g(y)。
则一个常见的思路是直接数论分块。
在可以快速求出 f, g 块筛的情况下，我们可以将其转化为：
其中 S_f(n) = \displaystyle\sum_{i = 1}^n f(i)。
事实上我们也可以从双曲线下整点计数的角度来解释这个问题：
- 给定双曲线 l : xy = n。
- 求第一象限内所有在 l 下方或在 l 上的点 (x, y) 的 f(x) g(y) 之和。
考虑在 l 上取点 (x_0, y_0)，则我们可以将原问题容斥为：
即我们可以把答案表示为：
一般地，取 x_0 = y_0 = \sqrt{n}，时间复杂度为 O(\sqrt{n})，与直接数论分块相同。
需要注意的是理论最优的 (x_0, y_0) 可能不是整点，此时取 x_0 为整点，y_0 = \lfloor \frac{n}{x_0} \rfloor 即可。
那它的优势在哪里呢？
- 除法运算次数较少，因而常数较小。
- 计算两个求和符号的时间复杂度不同时可以通过调整 x_0, y_0 取得更优时间复杂度。
事实上，上面的双曲线可以是任意的 l : x^p y^q = n，做法本质相同。
下面我将通过两个例子说明这两点。
本题差分后即为数论分块的最基本形式：求 \displaystyle\sum_{i = 1}^n \lfloor \frac{n}{i} \rfloor，也即上文中 f(n) = g(n) = 1 的情况。
此时 S_f(n) = S_g(n) = n，于是按照上式直接实现即可。
总用时 878ms（未精细实现），跑进了最优解第一页。
两问本质相同，下面只讲第一问的做法。
首先给出结论：任意一个 Powerful Number 都可以被唯一的表示成 x^2 y^3 的形式，其中 y 无平方因数。证明略去。
于是本题可以转化为 l : x^2 y^3 = n，f(n) = 1，g(n) = \mu^2(n) 的情况。
接下来有两个思路：
- 直接使用前述方法
还是取一个点 (x_0, y_0)，则我们可以将答案表示为：
考虑预处理 \max(\sqrt[6]{n}, y_0) 范围内的 \mu，然后单次 O(\sqrt[3]{n}) 地求 S_{\mu^2}(n)，则时间复杂度为 O(n^{\frac{1}{9}} x_0^{\frac{7}{9}} + \max(\sqrt[6]{n}, y_0))。当 x_0 = n^{\frac{2}{13}}，y_0 = n^{\frac{3}{13}} 取得最优时间复杂度为 O(n^{\frac{3}{13}})。
- 先化简 \mu^2
原式 = \displaystyle\sum_{x^2 y^3 \leq n} \sum_{d^2 \mid y} \mu(d) = \displaystyle\sum_{d = 1}^{\lfloor \sqrt[6]{n} \rfloor} \mu(d) \sum_{x^2 y^3 \leq \lfloor \frac{n}{d^6} \rfloor} 1。
后面的求和符号是一个 l : x^2 y^3 = n，f(n) = g(n) = 1 的问题，不难在 O(\sqrt[5]{\frac{n}{d^6}}) 的时间复杂度内解决。
预处理 O(\sqrt[6]{n}) 内的 \mu 即可。时间复杂度为 O(\sqrt[5]{n})。
我对思路 2 的实现总用时 110ms（未精细实现），拿到了最优解。