tqyaaaaang's Blog

洲阁筛

来讲讲求某些积性函数前缀和的黑科技。
这次讲洲阁筛。

推荐任之洲的2016年国家集训队论文。

前置技能

你需要知道下列东西来理解洲阁筛,这里就不详细讲了,百度一下应该会有很多的好的博客的,或者上面的论文中也有提到。

  • 数论函数
  • 积性函数
  • 狄利克雷卷积

洲阁筛

不得不说,洲阁筛比杜教筛要麻烦,但是适用范围更广。

洲阁筛要求对于任意质数 \(p\),\(f(p)\) 为一个关于 \(p\) 的低阶多项式,再对于满足 \(f(p^c) \le n\) 的任意指数 \(c\),\(f(p^c)\)可以较快速算出,则洲阁筛可以在\(\Theta(\frac{n^{\frac{3}{4}}}{\log{n}})\)复杂度内求出
$$ F(n) = \sum_{i=1}^n{f(i)} $$

一些规定

  • 设小于等于\(\sqrt{n}\)的质数有\(m\)个,升序排列后设为\(p_1, p_2, p_3, \ldots, p_m\)。这个可以线性筛\(\Theta{\sqrt{n}}\)预处理。
  • 设集合\(S\)为 \( S = \{ x \ | \ \exists \ y \in [1,n], x = \lfloor \frac{n}{y} \rfloor \} \)
  • 设 \( \forall p \text{ is a prime} \),\( f(p) = \sum_{i=0}^{k_m} {poly\_a_i * p^i}\),\(k_m\) 应不太大。

引理

引理1. 对于任意正整数\(i \in [1,n]\),\(\lfloor \frac{n}{i} \rfloor\)只有\(\Theta(\sqrt{n})\)种取值,即: \( |S| = \Theta ( \sqrt{n} ) \)。
证明: 这个比较显然。

  • 对于 \(i \le \sqrt{n}\),显然 \(\lfloor \frac{n}{i} \rfloor\) 只有 \(\Theta(\sqrt{n})\) 种取值。
  • 对于 \(i > \sqrt{n}\),有 \(\lfloor \frac{n}{i} \rfloor\ < \sqrt{n}\),\(\lfloor \frac{n}{i} \rfloor\) 也只有 \(\Theta(\sqrt{n})\) 种取值。

引理2. 对于正整数\(a, b, x, y, z\),若 \(\lfloor \frac{x}{a} \rfloor = y\), \(\lfloor \frac{y}{b} \rfloor = z\),则 \(\lfloor \frac{x}{ab} \rfloor = z\),即 \(\lfloor \frac{\lfloor \frac{x}{a} \rfloor}{b} \rfloor = \lfloor \frac{x}{ab} \rfloor\)。
证明: 设 \(x = kab + c\),\(c < ab\),即 \(k = \lfloor \frac{x}{ab} \rfloor\),则 \(y = kb + \lfloor \frac{c}{a} \rfloor\),由于 \(c < ab\),故 \(\lfloor \frac{c}{a} \rfloor < b\),则 \(\lfloor \frac{y}{b} \rfloor = k\)。

引理3. \( \forall x \in S, \ y \in [1,x], \ \lfloor \frac{x}{y} \rfloor \in S \)。
证明: 由集合\(S\)的定义知,\( \exists z \in [1,n], x = \lfloor \frac{n}{z} \rfloor \),于是由引理2,知 \( \lfloor \frac{x}{y} \rfloor = \lfloor \frac{\lfloor \frac{n}{z} \rfloor}{y} \rfloor = \lfloor \frac{n}{zy} \rfloor \)。又由于 \(y \le x\),故 \(\lfloor \frac{x}{y} \rfloor = \lfloor \frac{n}{zy} \rfloor \ge 1 \),所以 \( \lfloor \frac{n}{zy} \rfloor \in S \),故 \(\lfloor \frac{x}{y} \rfloor \in S\)。

这三个引理是洲阁筛优化的基础。

转化

由于每个小于\(n\)的数最多只有1个大于\(\sqrt{n}\)的质因子,故可以把数分为有无大于\(\sqrt{n}\)的质因子两类来考虑。
于是可以得到下列式子:
$$
F(n) = \left( \sum_{\substack{i \le n \\ i \text{ doesn't have a prime factor } > \sqrt{n}}} {f(i)} \right) + \left( \sum_{\substack{i \le n \\ i \text{ doesn't have a prime factor } > \sqrt{n}}} { \left( f(i) * \sum_{\substack{\sqrt{n} < p \le { \lfloor \frac{n}{i} \rfloor } \\ p \text{ is a prime number}}} {f(p)} \right) } \right)
$$
可以看出只有 \(i \le \sqrt{n}\) 时,\(\lfloor \frac{n}{i} \rfloor \ge \sqrt{n}\),又由于 \(\forall i \le \sqrt{n}\) 必然没有 \(> \sqrt{n}\) 的因子,故可以化为:
$$
F(n) = \left( \sum_{\substack{i \le n \\ i \text{ doesn't have a prime factor } > \sqrt{n}}} {f(i)} \right) \ + \ \left( \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} { \left( f(i) * \sum_{\substack{\sqrt{n} < p \le { \lfloor \frac{n}{i} \rfloor } \\ p \text{ is a prime number}}} {f(p)} \right) } \right)
$$
故原问题就可以转化成分别求前面和后面部分。

Part 1. 前半部分

先求 \(\sum_{\substack{i \le n \\ i \text{ doesn't have a prime factor } > \sqrt{n}}} {f(i)}\)。
考虑一个DP。
设 \(f_{1}(i,j)\) 为\([1,j]\)中只包含 \(p_i, \ldots, p_m\) 这几种质因子的数\(x\)的\(f(x)\)之和,即
$$
f_1(i,j) = \sum_{x \le j, \ x = p_i^{e_i}p_{i+1}^{e_{i+1}} \cdots p_m^{e_m} } {f(x)}
$$
则\(f_1(1,j)\)即为要求的值。
考虑转移,考虑第\(i\)个质数的情况,可以得到一个转移的式子:
$$
f_1(i,j) = f_1(i+1,j) + \sum_{e \ge 1} { \left( f(p_i^e) * f_1(i+1,\lfloor \frac{j}{p_i^e} \rfloor) \right) }
$$
边界情况显然\(f_1(m+1,i) = 1\) ( 就只有1可以是可以的 )。
根据引理3,我们只需要对 \(j \in S\) 进行DP就行了,这样一定有 \(\lfloor \frac{j}{p_i^e} \rfloor \in S \)。假设质数的密度近似为 \(\frac{1}{\log {n}}\), 于是状态数就变成了 \(\Theta(\frac{n}{\log{n}})\)。这个\(\sum\)带来的影响不是很大,因此转移可以近似是 \(\Theta(1)\)的,所以直接朴素实现就是\(\Theta(\frac{n}{\log{n}})\)的。

考虑优化这个DP。
可以发现,当 \(p_i > j\) 的时候,\(f_1(i,j) = 1\) ( 和边界情况相同,只有1是可以的 )。这并不能带来太多优化。但是下一步可以发现当 \(p_i^2 > j\) 时,\( p_{i+1} > \lfloor \frac{j}{p_i} \rfloor \),此时转移可以变为
$$
f_1(i,j) = f_1(i+1,j) + f(p_i)
$$
显然当 \(p_i^2 > j\) 的时候,\( \forall i' > i, p_{i'}^2 > j \),于是当 \(p_i^2 > j\)的时候可以不转移,而可以直接计算 ( 设 \(\le j\) 的最小质数为第 \(j'\) 个质数:
$$
f_1(i,j) = \left( \sum_{k=i}^{\min (j',m)} { f(p_k) } \right) + 1
$$
注意这里最后要 \(+1\) 是因为有边界情况 \(f_1(m+1,i) = 1\)。这是可以预处理前缀和 \(\Theta(1)\) 解决的,因此可以干脆不转移这些状态,直接在其它状态转移需要的时候 \(\Theta(1)\) 算一下就行了。这样对于 \( x \in S \),需要处理的质数不超过 \( \sqrt{x} \),状态数约为 \( \Theta(\frac{\sqrt{x}}{\log {x}}) \) 个 ( \(\frac{1}{\log{\sqrt{x}}}\) 与 \(\frac{1}{\log{x}}\) 同阶 )。即加起来为 \(\sum_{x \in S} { \Theta ( \frac{\sqrt{x}}{\log{x}} ) }\),可以用积分得到需要转移的状态数约为 \(\Theta(\frac{n^{\frac{3}{4}}}{\log {n}})\) 个,具体证明就不详细讲了,任之洲的论文里面有。转移仍然是 \(\Theta(1)\) 的,于是复杂度降为了 \(\Theta(\frac{n^{\frac{3}{4}}}{\log {n}})\)。

Part 2. 后半部分

先考虑求 \(\sum_{\substack{\sqrt{n} < p \le { \lfloor \frac{n}{x} \rfloor } \\ p \text{ is a prime number}}} {f(p)}\)。
同样的考虑DP。
设 \(f_2(i,j)\) 为 \([1,j]\) 中与 \(p_1, p_2, \ldots, p_i\) 这些质数 ( 前 \(i\) 个质数 ) 互质的数的 \(f\) 之和,即
$$
f_2(i,j) = \sum_{x \le j, \ \gcd(x,p_1 p_2 \cdots p_i)==1 } {f(x)}
$$
这样 \( \forall t \in S \bigcap \ [\lfloor \sqrt{n} \rfloor+1,n], \left( f_2(m,t) - f_2(m,1) \right) \) 就为所求的结果。由于积性函数 \(f\) 必然有 \( f(1) = 1 \),故就是要求 \( \forall t \in S \bigcap \ [\lfloor \sqrt{n} \rfloor+1,n], \left( f_2(m,t) - 1 \right) \) 。
边界情况 \( f_2(0,j) = \sum_{x=1}^j { f(x) } \)。这是什么,这就是我们要求的 \( f \) 的前缀和!!!所以这么DP不好求边界,所以不能这么DP。

考虑改一下DP的状态,由于最后DP完了之后余下的只是质数的 \(f\) 的和,所以考虑把质数 \(p\) 的函数值 \( f(p) \) 写成一个低次多项式 ( 想起之前说的洲阁筛的要求了吧 ),对于多项式的每一次项分开处理,最后分别乘一个相应的多项式的系数加起来就是答案。由于DP完了之后余下的只是质数的 \(f\) 的和,所以其它非质数的值为多少不会影响答案,因此可以假设也满足这个多项式。多项式的次数越小,就越快。

设当前考虑求的是 \(k\) 次项 ( \( k \) 一定不会很大 ),则原问题变成了求\(\sum_{\substack{\sqrt{n} < p \le { \lfloor \frac{n}{x} \rfloor } \\ p \text{ is a prime number}}} {p^k}\)。
改一下之前的那个DP,设 \(f_{2,k}(i,j)\) 为 \([1,j]\) 中与 \(p_1, p_2, \ldots, p_i\) 这些质数 ( 前 \(i\) 个质数 ) 互质的数 \(x\) 的 \(x^k\) 之和,即
$$
f_{2,k}(i,j) = \sum_{x \le j, \ \gcd(x,p_1 p_2 \cdots p_i)==1 } {x^k}
$$
同样 \( \forall t \in S \bigcap \ [\lfloor \sqrt{n} \rfloor+1,n], \left( f_{2,k}(m,t) - 1 \right) \) 就为所求的结果。
这时候边界 \( f_{2,k}(0,j) = \sum_{x=1}^j { x^k } \),就可以用插值来完成了 ( 甚至可以手推公式 )。由于 \( k \) 不大,所以插值的复杂度不太影响。
然后就可以转移了,转移考虑不与 \(p_i\) 互质的部分。
$$
f_{2,k}(i,j) = f_{2,k}(i-1,j) - p_i^k * f_{2,k}(i-1, { \lfloor \frac{j}{p_i} \rfloor } )
$$
需要求的是 \( \forall t \in S \bigcap \ [\lfloor \sqrt{n} \rfloor+1,n], f_{2,k}(m,t) \),于是同 Part 1 里面的,这里也只需要转移 \(j \in S\) 的部分就行了。状态同样是 \(\Theta ( \frac{n}{\log n} )\) 的,考虑用类似的方法优化。
同样可以发现,当 \(p_{i+1} > j\) 的时候,\(f_{2,k}(i,j) = 1\) ( 只有1是可以的 ),然后当 \(p_i^2 > j\) 时,\( p_i > \lfloor \frac{j}{p_i} \rfloor \),此时转移可以变为
$$
f_{2,k}(i,j) = f_{2,k}(i-1,j) - p_i^k
$$
显然当 \(p_i^2 > j\) 的时候,\( \forall i' > i, p_{i'}^2 > j \),于是当 \(p_i^2 > j\)的时候就可以不转移了,记一下每一个 \(j\) 最后一个转移了的位置 \(i\_last_j\),于是可以直接计算了:
$$
f_{2,k}(i,j) = f_{2,k}(q_j,j) - \sum_{x=i\_last_j+1}^{i} {p_x^k}
$$
也是可以预处理前缀和解决的,于是就可以 \(\Theta(1)\) 求了。与上面同样的优化方法,就可以做到 \(\Theta(\frac{n^{\frac{3}{4}}}{\log n})\)了。

于是就可以\(\Theta(\frac{n^{\frac{3}{4}}}{\log n})\) 筛出所有 \(t \in S\) 的 \(\sum_{\substack{\sqrt{n} < p \le { \lfloor \frac{n}{t} \rfloor } \\ p \text{ is a prime number}}} {f(p)}\), \( \Theta(\sqrt{n}) \) 线性筛筛出 \( [1,{\lfloor \sqrt{n} \rfloor}] \) 的 \( f \) 的值,再直接 \( \Theta(\sqrt{n}) \) 套到原式的\(\left( \sum_{i=1}^{\sqrt{n}} { \left( f(i) * \sum_{\substack{\sqrt{n} < p \le { \lfloor \frac{n}{i} \rfloor } \\ p \text{ is a prime number}}} {f(p)} \right) } \right)\)上面就可以求出后半部分的值了。

合并

然后就可以合并两个部分的答案,就可以了。
$$
F(n) = f_1(1,j) + \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} { \left( f(i) * \sum_{j=0}^{k_m} { \left( poly\_a_j * f_{2,j}(m,{ \lfloor \frac{n}{i} \rfloor }) \right) } \right) }
$$

分析

时间复杂度: 两个部分都是 \(\Theta(\frac{n^{\frac{3}{4}}}{\log n})\) 的,预处理都是 \(\Theta(\sqrt{n})\) 的,所以总时间复杂度就是 \(\Theta(\frac{n^{\frac{3}{4}}}{\log n})\) 的了。
空间复杂度: 记前缀和是 \(\Theta(\sqrt{n})\) 的,DP的时候可以用滚动数组优化到 \(\Theta(\sqrt{n})\),所以总空间复杂度是 \(\Theta(\sqrt{n})\)。

UPD: 洲阁筛常数巨大,代码量巨大,尽管复杂度看上去好一些,但是实际跑得很慢。所以能用杜教筛的时候尽量用杜教筛吧。

Tianqi Yang

View Comments
Navigation