【学习笔记】筛法

Unnamed114514 · 2024-07-18 17:21:29 · 算法·理论

link

前置知识

积性函数

积性函数：对于数论函数 f，若 \forall \gcd(a,b)=1,f(ab)=f(a)f(b)，则称 f 为积性函数。
完全积性函数：对于数论函数 f，若 \forall a,b,f(ab)=f(a)f(b)，则称 f 为完全积性函数。

容易发现 f(1)=1。

Dirichlet 卷积

对于两个数论函数 f,g，它们的 Dirichlet 卷积为：(f*g)(n)=\sum\limits_{d\mid n} f(i)g(\dfrac{n}{i})。

Dirichlet 单位元：\epsilon，满足对于任意数论函数 f，f*\epsilon=f，有 \epsilon(n)=[n=1]

常见函数的 Dirichlet 卷积：

\mu*I=\epsilon
\varphi*I=id
\mu*id=\varphi

其中 id(n)=n,I(n)=1。

数论分块

考虑 \dfrac{n}{i} 的不同取值数：当 i\le\sqrt n 时，有 \sqrt n 个取值；当 i>\sqrt{n} 时，\dfrac{n}{i}<\sqrt n，有 \sqrt n 个取值。

结论：\lfloor\dfrac{n}{j}\rfloor=\lfloor\dfrac{n}{i}\rfloor 的最大的 j 为 \rfloor\dfrac{n}{\lfloor\dfrac{n}{i}\rfloor}\rfloor。

证明：令 k=\lfloor\dfrac{n}{i}\rfloor，那么易知 k\le\dfrac{n}{i}\to\lfloor\dfrac{n}{k}\rfloor\ge\lfloor\dfrac{n}{\frac{n}{i}}\rfloor=i。那么 j_{\max}=\lfloor\dfrac{n}{k}\rfloor。

还没证完，下证 \lfloor\dfrac{n}{\lfloor\frac{n}{k}\rfloor}\rfloor=\lfloor\dfrac{n}{i}\rfloor=k。

motivation：a=b 等价于 a\ge b\land a\le b 。

注意到：

k\times \lfloor\dfrac{n}{k}\rfloor\le n\to\lfloor\dfrac{n}{\lfloor\frac{n}{k}\rfloor}\rfloor\ge k

\lfloor\dfrac{n}{k}\rfloor\ge i\to \lfloor\dfrac{n}{\lfloor\frac{n}{k}\rfloor}\rfloor\le k

故 \lfloor\dfrac{n}{\lfloor\frac{n}{k}\rfloor}\rfloor=k 。

杜教筛

求积性函数 f 的前缀和：S(n)=\sum\limits_{i=1}^n f(i)。

我们构造另一个函数 g，用 Dirichlet 卷积式展开 (f*g)。

\sum\limits_{i=1}^n(f*g)(i)=\sum\limits_{i=1}^n \sum\limits_{d\mid i}f(i)g(\dfrac{i}{d})=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)=\sum\limits_{d=1}^n g(d)S(\lfloor\dfrac{n}{d}\rfloor)

上文说过 g(1)=1，那么有 S(n)=g(1)S(n)=\sum\limits_{d=1}^ng(d)S(\lfloor\dfrac{n}{d}\rfloor)-\sum\limits_{d=2}^n g(d)S(\lfloor\dfrac{n}{d}\rfloor)。

因此有：

S(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{d=2}^n g(d)S(\lfloor\dfrac{n}{d}\rfloor)

通过数论分块，S(\lfloor\dfrac{n}{d}\rfloor) 只有 O(\sqrt{n}) 个不同的取值，每一个取值对应一段 d 的区间。

那么我们只需要快速求出 (f*g),g 的前缀和，就能进一步求出 f 的前缀和。

这里的复杂度是 O(n^{\frac{3}{4}}) 的。

可以考虑线性筛求出前 m=n^\frac{2}{3} 的 S，这样的话时间复杂度就优化到了 O(n^{\frac{2}{3}})。

答案可以打个记忆化。

【模板】杜教筛

考虑 \varphi*I=id,\mu*I=\epsilon，带入式子即可。

code

Powerful Number（简称 PN）筛

定义：数 k=\prod p_i^{m_i} ，若 \forall m_i>1，那么 k 就是 PN，特别地，1 是 PN。

性质 1：对于任意 PN k，\exists a,b,k=a^2b^3。

证明：若 m_i 为偶数，就把 m_i 放到 a^2 里；否则就先放一个 b^3，把 m_i 转化为偶数。

性质 2：n 以内的 PN 有 O(\sqrt{n}) 个。

如何求出 n 以内的所有 PN 呢？

从定义出发，考虑质因数分解的形式，我们可以筛出 \sqrt{n} 以内的质数，枚举每个数的指数即可。

一共只有 \sqrt{n} 个 PN，所以这里只会搜 O(\sqrt{n}) 次。

这里我们需要构造一个积性函数 g，使得对于任意质数 p，g(p)=f(p)。

然后再构造另一个积性函数 h，满足 h*g=f，容易得到 h(p)=0。

因为 h 是积性函数，所以 h 只在 PN 处有值。

S(n)=\sum\limits_{i=1}^n \sum\limits_{d\mid i} g(\dfrac{i}{d})h(d)=\sum\limits_{d=1}^n h(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}g(i)=\sum\limits_{d=1}^n[d \in\mathbb P\mathbb N]h(d)G(\lfloor\dfrac{n}{d}\rfloor)

因为 $h$ 是积性函数，所以我们只需要算 $h(p^m)$ 的值即可。 $f(p^m)=\sum\limits_{i=0}^m h(p^i)g(p^{m-i})\to h(p^m)=f(p^m)-\sum\limits_{i=0}^{m-1}h(p^i)g(p^{m-i})

注意到如果我们计算过 G(n)，那么在记忆化之后 G(\lfloor\dfrac{n}{d}\rfloor) 都已经被算过了，所以时间复杂度是 O(n^{\frac{2}{3}}) 的。

【模板】Min_25 筛

构造 g(i)=i\times\varphi(i)。

杜教筛方面，考虑 g*id：(g*id)(n)=\sum\limits_{d\mid n} d\times\varphi(d)\times \dfrac{n}{d}=n\times\sum\limits_{d\mid n}\varphi(d)=n^2。

那么 \sum (g*id)(i)=\dfrac{n(n+1)(2n+1)}{6}。

code

洲阁筛

要求 f(p^m)(p\in\mathbb P,m\in\mathbb N)（\mathbb P 为质数集）是关于 p 的低阶多项式。

motivation：对于每个数，>\sqrt{n} 的质因子最多只有 1 个。

考虑分治，按照是否有 >\sqrt n 的质因子分成两组求和：

\sum\limits_{i=1}^nf(i)=\sum\limits_{i=1}^n[\exist d\in(\sqrt{n},n]\bigcup\mathbb P,d\mid i]f(i)+\sum\limits_{i=1}^n[\forall d\in(\sqrt{n},n]\bigcup\mathbb P,d\nmid i]f(i)

第一部分

令 m 为 p_m\le\sqrt n\land p_{m+1}>\sqrt n。

转化问题：枚举 d。

\sum\limits_{i=1}^n[\exist d\in(\sqrt{n},n]\bigcup\mathbb P,d\mid i]f(i)=\sum\limits_{i=1}^{\sqrt{n}}\sum\limits_{d=\sqrt{n}+1}^{\lfloor\frac{n}{i}\rfloor}[d\in\mathbb P]f(i\times d)

注意到 \gcd(i,d)=1，故原式等价于：\sum\limits_{i=1}^{\sqrt{n}}f(i)\sum\limits_{d=\sqrt{n}+1}^{\lfloor\frac{n}{i}\rfloor}[d\in\mathbb P]f(d)

把所有质数预处理出来求前缀和可以得到 O(\dfrac{n}{\log n}) 的做法，但这显然不是我们想要的。

motivation：对于每个合数，一定会有 \le \sqrt{n} 的因子。

那么 d 就是 [\sqrt{n}+1,\lfloor\dfrac{n}{i}\rfloor] 中与 \le\sqrt n 的质数都互质的数。

我们令 g(t,k)=\sum\limits_{i=1}^{k}[\forall j\in[1,t],\gcd(p_j,i)=1]f(i)，其中 p_j 表示第 j 个质数。

人话：[1,k] 中 \ge p_t 的质数的 f 的和加一（不要忘了 1！），因为 \le p_t 的质数都在 p_{[1,t]} 中。

答案即求 \sum\limits_{i=1}^{\sqrt n}f(i)(g(m,\lfloor\dfrac{n}{i}\rfloor)-1)。

边界 g(0,k)=\sum\limits_{i=1}^kf(i)，转移 g(t,k)\gets g(t-1,k)-f(p_t)\times g(t-1,\lfloor\dfrac{k}{p_t}\rfloor)。

注意到 p_{t+1}>k\to g(t,k)=1。

若 p_t>\lfloor\dfrac{k}{p_t}\rfloor\to p_t^2>k，回代递推式知 g(t,k)\gets g(t-1,k)-f(p_t)。

那么我们只需要找那些 p_t^2\le k 的质数即可，当 p_t^2>k 停止转移。记此时的 t 为 t_k，有：g(t,k)\gets g(t_k-1,k)-\sum\limits_{i=t_k}^{t}f(p_k)。

这个时候我们就只需要处理 \sqrt n 以内质数的 f 的前缀和了！

这一部分时间复杂度是 O(\dfrac{n^{\frac{3}{4}}}{\log n}) 的。

第二部分

类似地，定义 h(i,j) 表示 \sum\limits_{k=1}^j[\exists c_1,c_2,\cdots c_m,i=\prod\limits_{t=i}^m p_t^{c_t}]f(i)。

人话：[1,j] 中质因子都在 [p_t,p_m] 的数的 f 的和。

答案即求： h(1,n)。

边界：h(m+1,j)=1，转移：h(i,j)\gets h(i+1,j)+\sum\limits_{k=1}^{\log_{p_i}j}f(p_i^k)h(i+1,\lfloor\dfrac{j}{p_i^k}\rfloor)。

直接暴力算的话复杂度也是 O(\dfrac{n}{\log n}) 的。

考虑用和第一部分一样的优化：当 p_i>j 时，满足条件的数只有 1。

时间复杂度 O(\dfrac{n^\frac{3}{4}}{\log n})。

Summary：洲阁筛本质上是一个 dp 的过程。

Min_25 筛

~~开通会员即可查看全文，最低仅需 0.3元/天！~~

要求 f(p)(p\in\mathbb P)是关于 p 的低阶多项式，且 f(p^m) 可以快速求解。

令 h(x) 表示 x 的最小质因子，特别地，h(1)=1。

对质数和合数的贡献分开来求。

质数

因为是低阶多项式，所以可以枚举次数，然后进行累加，不妨考虑一项，令 f'=[x^n]x^n。

令 g(n,j)=\sum\limits_{i=1}^n[h(i)>p_j\lor i\in\mathbb P]f'(i)。

人话：有质因子都大于 p_j 和 n 以内所有质数的 f' 的和，那么求的就是 g(n,m)。

有了洲阁筛的铺垫，容易想到从 g(n,j-1) 递推到 g(n,j)。

这时候完全积性函数的优势就体现出来了：括号内仍然包含 p_j 因子，但是由于是完全积性函数，所以可以直接相乘！

这玩意本质上就是洲阁筛的第一部分，时间复杂度 O(\dfrac{n^\frac{3}{4}}{\log n})。

合数

定义 S(n,j)=\sum\limits_{i=1}^n[h(i)>p_j]f(i)。

人话：质因子都大于 p_j 的数的 f 的和。

求的就是 S(n,0)+1。

因为这里只有积性函数的性质，所以我们必须枚举指数。

S(n,j)=\sum\limits_{i=j+1}^m\sum\limits_{k=1}^{\log_{p_i} n} f(p_i^k)(S(\lfloor\dfrac{n}{p_i^k}\rfloor,i)+[k>1])

值得注意的是，因为 S 不会算到 1，所以不会计算到质数。

在 zzt 的论文中，这玩意时间复杂度是 O(n^{1-\epsilon}) 的。

Summary：Min_25 筛本质上也是一个 dp 的过程。

O(n^{\frac{2}{3}})