杜教筛 & Powerful Number 筛

LarsWerner / 2023-05-03 / 原文

迪利克雷卷积

对于数论函数 \(F\)，\(G\)，我们定义迪利克雷卷积的结果 \(H=F*G\) 为

\[H_n=\sum_{d\mid n}F_d G_\frac{n}{d} \]

有些好的性质，比如：对于积性函数 \(F\) 与 \(G\)，其迪利克雷卷积 \(F*G\) 也是积性函数；而在迪利克雷卷积的意义下，积性函数 \(F\) 的逆也是积性函数（逆满足 \(F^{-1}*F=e\)）。

当公因式是完全积性函数时，点乘对迪利克雷卷积有分配律（下式中要求 \(X\) 为完全积性函数）：

\[(A\cdot X)*(B\cdot X)=(A*B)\cdot X \]

杜教筛

假设我们对于积性函数 \(f\)，要求出 \(f\) 的前缀和，即 \(\sum_{i\le n}f_i\)。我们找到积性函数 \(g\)，设 \(h=f*g\)。设 \(S_f\) 表示 \(f\) 的前缀和，则有：

\[\begin{aligned} S_h(n)&=\sum_{i=1}^{n}\sum_{d\mid i}g_df_{i/d}\\ &=\sum_{d=1}^{n}g_d\sum_{i=1}^{\lfloor n/d\rfloor }f_i\\ &=\sum_{d=1}^{n}g_dS_f(\lfloor n/d\rfloor) \end{aligned} \]

把 \(d>1\) 的项提到左边去，得到

\[S_f(n)=S_h(n)-\sum_{d=2}^{n}g_dS_f(\lfloor n/d\rfloor) \]

我们把 \(\le n^{2/3}\) 的 \(S_f\) 全部线性筛处理了，然后按上面的式子递归算，最后得到的处理 \(S_f\) 的复杂度是 \(O(n^{2/3})\)。

一些常见恒等式

关于 \(\mu\)：

\(\mu*I=\epsilon\)
\((\mu \cdot id_k)*id_k=(\mu\cdot id_k)*(I\cdot id_k)=(\mu \cdot I)*id_k=\epsilon\)
\(\mu^2=\sum_{d^2\mid n} \mu(d)\)
有了这个就可以求 \(\mu^2\) 的前缀和，即

\[\begin{aligned} \sum_{i=1}^{n} \mu(i)^2&=\sum_{i=1}^{n}\sum_{d^2\mid i}\mu(i)\\ &=\sum_{d=1}^{\sqrt{n}} \mu(d)\sum_{d^2\mid i}1\\ &=\sum_{d=1}^{\sqrt{n}} \mu(d)\lfloor\frac{n}{d^2}\rfloor \end{aligned} \]
然后就可以 \(O(\sqrt n)\) 求了。

关于 \(\varphi\)：

\(\varphi*I=id\)
\((\varphi \cdot id_k)*id_k=(\varphi\cdot id_k)*(I\cdot id_k)=(\varphi \cdot I)*id_k=id_{k+1}\)
\(\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\)
不断地带 \(\varphi(x)=x\prod_{d\mid x}\frac{d-1}{d}\) 即可。

BZOJ3512 DZY Loves Math IV

对于积性函数的性质的应用。

一个比较有趣的技巧：对于 \(x\)，设其为 \(x=\prod p_i^{q_i}\)，我们设 \(q=\prod p_i\)，\(p=\frac{x}{q}\)，我们考虑直接求 \(\varphi\) 的式子，每个因数只有在第一次会有特殊处理，其他情况都是直接乘上，所以 \(\varphi(x)=p\varphi(q)\)，且对于任意 \(i\)，都有 \(\varphi(ix)=p\varphi(iq)\)。然后由于 \(q\) 每个数都只有一次项，所以有很多互质的性质，可以在积性函数上得以体现。

设 \(S(n,m)=\sum_{i=1}^{m}\varphi(i\times n)\)，我们把 \(n\) 拆成 \(pq\)，则有

\[\begin{aligned} S(n,m)&=\sum_{i=1}^{m}\varphi(iq)p\\ &=p\sum_{i=1}^{m}\gcd(i,q)\times \varphi(\frac{q}{\gcd(i,q)})\varphi(i)\\ &=p\sum_{i=1}^{m}\varphi(i)\varphi(\frac{q}{\gcd(i,q)})\sum_{d\mid \gcd(i,q)}\varphi(d)\\ &=p\sum_{i=1}^{m}\varphi(i)\sum_{d\mid i,d\mid q}\varphi(\frac{qd}{\gcd(i,q)})\\ &=p\sum_{i=1}^{m}\varphi(i)\sum_{x\mid i,x\mid q}\varphi(\frac{d}{x})\\ &=p\sum_{d\mid q}^{n}\varphi(\frac{q}{d})\sum_{d\mid i}^{m}\varphi(i)\\ &=p\sum_{d\mid q}^{n}\varphi(\frac{q}{d})S(d,\lfloor\frac{m}{d}\rfloor) \end{aligned} \]

然后直接递推即可，复杂度分析和杜教筛相似。

LOJ6686 Stupid GCD

求 \(\sum_{i=1}^{n}\gcd(\lfloor\sqrt[3]{i}\rfloor,i)\)。

考虑 \(n=k^3+1\) 的情况。如果不是的话后面应该还要有一项，那一项单独处理是类似（这么写只是因为一开始漏考虑了…）。

\[\begin{aligned} \sum_{i=1}^{n}\gcd(\lfloor\sqrt[3]{i}\rfloor,i) &=\sum_{i=1}^{n}\sum_{d\mid \lfloor\sqrt[3]{i}\rfloor,d\mid i} \varphi(d)\\ &=\sum_{i=1}^{k-1}\sum_{j=i^3}^{(i+1)^3-1}\sum_{d\mid i,d\mid j}\varphi(d)\\ &=\sum_{d=1}^{k-1}\varphi(d)\sum_{d\mid i}^{k-1}\lfloor\frac{i^3+3i^2+3i}{d}\rfloor-\lfloor\frac{i^3-1}{d}\rfloor\\ &=\sum_{d=1}^{k-1}\varphi(d)\sum_{i=1}^{\lfloor\frac{k-1}{d}\rfloor}3di^2+3i+1\\ &=3\sum_{d=1}^{k-1}\varphi(d)d\sum_{i=1}^{\lfloor\frac{k-1}{d}\rfloor}i^2+\sum_{d=1}^{k-1}\varphi(d)\sum_{i=1}^{\frac{k-1}{d}}3i+1 \end{aligned} \]

\(\varphi\cdot id_k\) 显然是可以杜教筛的（上面说过），于是就可以做了。

Powerful Number 筛

定义一个数为 Powerful Number，当且仅当它的每个质因子次数都 \(>2\)。由于每个 PN 都可以表示成 \(x^2y^3\)，于是可以发现 \(\le n\) 的 PN 个数为 \(O(\sqrt n)\)。

我们需要求出积性函数 \(f(x)\) 的前缀和，考虑构造积性函数 \(g(x),h(x)\)，满足 \(f=g*h\)，且 \(f(p)=g(p)\)。此时我们发现 \(f(p)=g(p)h(1)+g(1)h(p)\)，由于 \(g(1)=h(1)=1\)，于是 \(h(p)=0\)。对于积性函数，如果它在质数处取 \(0\)，那么显然它只有在 PN 处才可能有值。

于是我们要求的

\[\sum_{i=1}^{n} f(i)=\sum_{ij} g(i)h(j)\\\ = \sum_{i\le n} h(i) \sum_{j=1}^{n/i} g(j) \]

由于 \(h\) 只在 PN 处有值，所以我们相当于只需要算 \(\sqrt{n}\) 个 \(g\) 的前缀和在 \(\lfloor \frac{n}{i} \rfloor\) 处的值即可。于是我们只需要对 \(g\) 做杜教筛即可。

还有一件事情，就是如何确定 \(h\)。我们按照 \(h\) 的定义式进行处理

\[f(p^k)=\sum_{i+j=k}g(p^i)h(p^j)\\ h(p^k)=f(p^k)-\sum_{i=0}^{k-1}h(p^i)g(p^{k-i}) \]

由于 PN 的质因子 \(p\) 一定 \(\le \sqrt n\)，于是就可以 \(O(\sqrt n\log^2 n)\) 求出所有所需的 \(h\) 了。

找 PN 的过程枚举每个 \(p\) 的次数，dfs 即可。

LG5325 【模板】Min25筛

题目中 \(f(p^k)=p^k(p^k-1)\)。于是 \(f(p)=p(p-1)\)。我们取积性函数 \(g=id\cdot \varphi\) 即可。前面说到过 \((id\cdot varphi)*id=id_2\)，直接杜教筛。

这题还有一个好处，由于 \(g=id\cdot \varphi\)，\(g(p^k)=(p-1)p^{2k-1}\)，我们可以手算出 \(h(p^k)=(k-1)p^k(p-1)\)。

LOJ6053 简单的函数

题目中 \(f(p^c)=p\oplus c\)。于是 \(f(p)=p\oplus 1\)，即在 \(p=2\) 时 \(f(p)=3\)，其余时候 \(f(p)=p-1\)。但是这个 \(g\) 的前缀和并不好求。这时候，我们考虑直接令 \(g(p)=\varphi\)，并且根据 \(h\) 的定义式修改 \(h\)。这时候的 \(h\) 就不符合只有 PN 处有值的性质了。但是我们发现增加的有值的地方只会是 PN 乘上 \(2\)。所以复杂度仍然正确。