亚线性筛

发表于 更新于 分类于 阅读次数：

亚线性筛，就是以低于线性的复杂度预处理一些线性信息的筛法统称。

目前我会杜教筛和 min25 还有 powerful number。

杜教筛

篇幅过长，点击此处。

min25

min25 筛是扩展埃氏筛，也可以筛一类（更复杂的）积性函数的前缀和，并且通常是同类亚线性筛中最快的一个。
而且灵活运用 min25 可以处理一些特殊的关于质因子的问题。

理论

假设要求 \(S(n) = \sum_{i=1}^n f(i)\) 。

min25 筛可大致分为两步。

Step 1

第一步处理的是 \(f\) 在质数上的取值的和。
令 \(F(x) = [x \in Prime] f(x)\) ，那么这一步的目标是筛出 \(F\) 的前缀和。
准确地讲，是 \(F\) 的前缀和函数 \(S_F\) 在每个形如 \(\frac{n}{d}\) 的数上的取值。

首先需要将 \(f(i)\) 拆成若干完全积性函数的和，
只需考虑 \(F\) ，也就是 \(f(p^k)\) 的取值。
如果是关于 \(p\) 的多项式，每个单项式对应的就是一个完全积性函数。

假设现在要筛一个完全积性函数 \(h\) ，要能快速计算出 \(S_h = \sum_{i=1}^n h(i)\) 。
这一步的主要思想是，一个一个枚举质数 \(p\) ，筛掉最小质因子为 \(p\) 的合数的取值。
而合数 \(x\) 的最小质因子为 \(p\) 的必要条件是 \(p^2 \leq x\) ，即 \(p \leq \sqrt{x}\) 。
那么只需要枚举 \(\sqrt{n}\) 以内的质数去筛即可。

假设现在筛掉了前 \(i - 1\) 个质因子得到一个这个值：

\[g(n, i - 1) = \sum_{x=1}^n [x \in Prime \; or \; minp(x) > P_{i-1}] h(x)\]

其中 \(P_i\) 表示 \(\sqrt{n}\) 以内第 \(i\) 个质数。

那么接下来要筛最小质因子为 \(P_i\) 的合数：

\[g(n, i) = g(n, i - 1) - \sum_{x=1}^n [minp(x) = P_i \; and \; x \notin Prime] h(x)\]

由于 \(h\) 是完全积性函数，\(P_i\) 可以直接提出来，得到（这里的除号表示整除）：

\[ \begin{equation} \begin{aligned} g(n, i) &= g(n, i - 1) - h(P_i) \sum_{x=1}^{n/P_i} [minp(x) \geq P_i] h(x) \\\\ &= g(n, i - 1) - h(P_i) (g(\frac{n}{P_i}, i - 1) - \sum_{x=1}^{n/P_i} [x \in Prime \; and \; minp(x) < P_i] h(x)) \\\\ &= g(n, i - 1) - h(P_i) (g(\frac{n}{P_i}, i - 1) - \sum_{j=1}^{i-1} h(P_j)) \\\\ &= g(n, i - 1) - h(P_i) (g(\frac{n}{P_i}, i - 1) - ph_{i - 1}) \\\\ \end{aligned} \end{equation} \]

其中 \(ph_i\) 就是 \(h\) 在前 \(i\) 个质数上的取值和，注意 \(P_i \leq \sqrt{n}\) ，这是可以直接筛的。

那么上面的式子就是 \(g\) 的递推式，不难发现第一维的取值都是 \(\frac{n}{d}\) 的形式，第二维可以滚动。
直接按照递推式算，就可以在 \(O(\sqrt{n} |P|)\) 的时间筛出需要的东西，也就是 \(g(n, |P|)\) 。
这还是不够的，需要优化，由于最小质因子的取值在根号以内，所以递推时只需考虑满足 \(n \geq P_i^2\) 的 \(g(n, i)\) 。
当 \(n < P_i^2\) 时，随着 \(i\) 的增大 \(g(n, i)\) 的值不会改变，由于是滚动数组，直接 skip 掉就好了。

update: 实现中并不需要单独维护 \(ph\) ，事实上直接在 \(g\) 中就能查到需要的 \(ph\) 。

Step 2

上面将每个完全积性函数的 \(g(n, |P|)\) 加起来，得到 \(S_F(n)\) ，表示 \(f\) 在质数上的取值 \(F\) 的前缀和。

仍然利用最小质因子，不同的是，上一步从所有的取值开始从小到大把对应的最小质因子的合数的贡献给删掉的到质数的取值。
那这一步能不能反过来，从质数的取值开始，从大到小把对应的最小质因子的合数的贡献给加上最后得到所有数的取值？

并不能，事实上是从空值开始，从大到小把对应的最小质因子的数的贡献加上最后得到所有数的取值，
合数可以递推并类似地利用积性函数的性质提出一个因子，质数则直接用上一步预处理的来算。

那么假设现在以及算上了比第 \(i\) 个更大的质数为最小质因子的数的值得到了这个：

\[S(n, i) = \sum_{x=1}^n [minp(x) > P_i] f(x)\]

不难推导出：

\[S(n, i)=S_F(n) - pf_i + \sum_{P_j < P_k \leq \sqrt{n}} \sum_{e>0,P_k^e \leq n}f(P_k^e)(S(\frac{n}{P_k^e}, k) + [e>1])\]

其中 \(pf_i\) 就是 \(f\) 在前 \(i\) 个质数上的取值和，注意 \(P_i \leq \sqrt{n}\) ，这是可以直接筛的。

同样地第一维的取值都是 \(\frac{n}{d}\) 的形式，但是第二维无法滚动，
但事实上后面的部分直接递归计算即可，以下是参考实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef long long lolong;
lolong S(lolong i, int j) {
	if(prime[j] > i) return 0;
	lolong res = S_F[id(i)] - pf[j];
	for(int k = j + 1; k <= p and 1ll * prime[k] * prime[k] <= i; k ++) {
		int e = 1;
		lolong pr = prime[k];
		while(pr <= i) {
			res += (prime[k] ^ e) * (S(i / pr, k) + (e > 1));
			pr *= prime[k];
			e ++;
		}
	}
	return res;
}

复杂度似乎是 \(O(\frac{n^{\frac{3}{4}}}{\log n})\) ，大概是能跑 \(10^{11}\) 的。

另外 min25 筛还有个树状数组的优化版本，也是 min25 本人引入的，复杂度 \(O(n^{\frac{2}{3}})\) ，
大概能跑 \(10^{13}\) ？
但很不常见，网上可供学习的资料很少，有兴趣可以直接看 min25 的博客。

Powerful number

这个在 OI 中用得少，我也只是做过两道题，大概提一下。

称 1 和每个质因子次数大于 1 的合数为 Powerful number 。
首先有个性质就是 \(n\) 以内的 Powerful number 数量是 \(O(\sqrt{n})\) 的。

还是筛数论函数 \(f\) 的前缀和 \(S\) ，需要构造两个函数 \(g, h\) 满足 \(f = g \cdot h\) 。
如果 \(g\) 只在 Powerful number 上有值并且 \(h\) 的前缀和 \(S_h\) 容易求或者可以筛的话，
由 \(S(n) = \sum_{i=1}^n \sum_{d|x} g(d) h(\frac{d}{x}) = \sum_{d=1}^n G(d) S_h(n/d)\)
可以通过枚举 Powerful number 快速计算答案。

至于枚举 Powerful number 的方法，注意到 Powerful number 的质因子都是 \(\sqrt{n}\) 以内的，
这可以通过反证法证明，如果有大于 \(\sqrt{n}\) 的质因子它的次数不可能超过 1 。
那么筛出 \(\sqrt{n}\) 以内的质数，再通过搜索枚举每个质数的次数即可。

如果 \(h(x)\) 前缀和可以 \(O(1)\) 求的话，复杂度是 \(O(n^{\frac{1}{2}})\) 。

如果 \(h(x)\) 前缀和可以 \(O(\sqrt x)\) 求的话，复杂度是 \(O(n^{\frac{1}{2}} \log n)\) ，5s 内 \(10^{13}\) 不成问题。