标签：lfloor right 筛法狄利克卷积 dfrac sum rfloor left

狄利克雷卷积

概念

对于数论函数 \(f,g\)，定义其狄利克雷卷积 \(h=f*g\)，满足：

\[h(n)=(f*g)(n)=\sum_{d\mid n} f(d)g\left(\dfrac{n}{d}\right) \]

运算律：

满足交换律，显然具有对称性。
满足结合律，等价于三个 \(d_i\) 贡献到 \(n\)。
满足加法的分配率。

常见数论函数：

\(\mathrm{I}\)，常函数，值恒为 \(1\)。
\(\mathrm{Id}_k\)，幂函数，值为 \(n^k\)。
\(\epsilon\)，狄利克雷卷积的单位元，除 \(\epsilon(1)=1\) 外其余均为 \(0\)。
\(\mu\)，莫比乌斯函数，狄利克雷卷积的逆元。
\(\varphi\)，欧拉函数。
\(\sigma_k\)，除数函数，定义 \(\sigma_k(n)=\sum_{d\mid n}d^k\)。

常见数论函数卷积变换

\(\mu *\mathrm{I}=\epsilon\)。
\(\varphi *\mathrm{I}=\mathrm{Id}\)
\(\mathrm{Id}_k *\mathrm{I}=\sigma_k\)
\(\mu* \mathrm{Id}=\varphi\)
\((\mu \cdot \mathrm{Id}_k)*\mathrm{Id}_k=\epsilon\)
\((\varphi\cdot \mathrm{Id}_k)*\mathrm{Id}_k=\mathrm{Id}_{k+1}\)

杜教筛

原理

求数论函数前缀和。

设 \(h=f*g,S=\sum f\)，容易推得：

\[\begin{aligned} \sum_{i=1}^n h(i)&=\sum_{i=1}^n \sum_{j\mid i} f(j)g\left(\dfrac{i}{j}\right)\\ &=\sum_{j=1}^n g(j)\sum_{i=1}^{\left\lfloor n/i\right\rfloor} f(i)\\ &=\sum_{i=1}^n g(i)S\left(\left\lfloor \dfrac{n}{i}\right\rfloor\right) \end{aligned} \]

整理一下可以写成：

\[g(1)S(n)=\sum_{i=1}^n h(i)-\sum_{i=2}^{n} g(i)S\left(\left\lfloor \dfrac{n}{i}\right\rfloor\right) \]

如果构造出可以快速计算前缀和的函数 \(g,h\)，就可以递归求解了。

时间复杂度

首先需要证明的是：

\[\left\lfloor\dfrac{\left\lfloor\tfrac{n}{a}\right\rfloor}{b}\right\rfloor=\left\lfloor\dfrac{n}{ab}\right\rfloor \]

设 \(\mathrm{RHS}=k\)，则有：

\[k\times ab\le n<(k+1)\times ab \]

于是：

\[k\times b\le \dfrac{n}{a}<(k+1)\times b \]

从而：

\[k\times b\le \left\lfloor\dfrac{n}{a}\right\rfloor<(k+1)\times b \]

\[k\le \dfrac{\left\lfloor\tfrac{n}{a}\right\rfloor}{b}<k+1 \]

即：

\[\left\lfloor\dfrac{\left\lfloor\tfrac{n}{a}\right\rfloor}{b}\right\rfloor=\left\lfloor\dfrac{n}{ab}\right\rfloor \]

这说明当我们整除分块向下递归时，递归到 \(n'=\left\lfloor \dfrac{n}{d}\right\rfloor\)，枚举 \(d'\) 得到 \(\left\lfloor \dfrac{n'}{d'}\right\rfloor=\left\lfloor \dfrac{\left\lfloor \tfrac{n}{d}\right\rfloor}{d'}\right\rfloor\)，一定可以表示为 \(\left\lfloor \dfrac{n}{k}\right\rfloor\) 的形式，而这一定在第一层递归时处理到（不考虑先后顺序），于是在记忆化的加持下，计算复杂度只需要考虑第一层递归即可。

设当前块长 \(i\)，对复杂度的贡献就是 \(O\left(\sqrt{\dfrac{n}{i}}\right)\)。

当 \(i> \sqrt{n}\) 时，第二层最大 \(O(n^{1/4})\)，所以总复杂度 \(O(n^{3/4})\)。

当 \(i\le \sqrt{n}\) 时，就写成：

\[\begin{aligned} T(n)&=O\left(\sum_{i=1}^{\sqrt{n}} \sqrt{\dfrac{n}{i}}\right)\\ &=O\left(\sqrt{n}\int_{1}^n \dfrac{1}{\sqrt{x}} \mathrm{d}x\right)\\ &=O(x^{3/4}) \end{aligned} \]

但较小的前缀和是可以预处理出的，假设预处理出了 \([1,n^k]\) 的前缀和，那么也就是只有 \(\dfrac{n}{i}>n^k\) 的部分才需要递归，也就变成：

\[\begin{aligned} T(n)&=O\left(n^k+\sum_{i=1}^{n^{1-k}} \sqrt{\dfrac{n}{i}}\right)\\ &=O\left(n^k+\sqrt{n}\int_{1}^{n^{1-k}} \dfrac{1}{\sqrt{x}}\mathrm{d}x\right)\\ &=O(n^k+n^{1-k/2}) \end{aligned} \]

取 \(k=\dfrac{2}{3}\) 得到理论最优复杂度 \(O(n^{2/3})\)。

整除分块时（无论嵌套几层）使用杜教筛求数论函数前缀和，由于所有询问的区间右端点为 \(\left\lfloor \dfrac{n}{\left\lfloor \tfrac{n}{d}\right\rfloor}\right\rfloor\)，可以表示为上述记忆化的形式，所以并不会增加复杂度。

常用构造

最常用的是 \(\mu *\mathrm{I}=\epsilon\) 以及 \(\varphi *\mathrm{I}=\mathrm{Id}\)。

在此基础上有：\((\mu\cdot \mathrm{Id}_k)*\mathrm{Id}_k=\epsilon\)，\((\varphi\cdot \mathrm{Id}_k) * \mathrm{Id}_{k}=\mathrm{Id}_{k+1}\)。

另外根据 \(\sigma_k\) 的定义有 \(\mathrm{Id}_k*\mathrm{I}=\sigma_k\)。

例题

Luogu-P5218 无聊的水题 II

容易发现是要求选出一个集合满足 \(\gcd=1\)。

设 \(F(n)\) 为值域 \([1,n]\) 的方案数，那么 \(\gcd=k\) 就是 \(F\left(\left\lfloor \dfrac{n}{k}\right\rfloor\right)\)，可以单步容斥。

\[F(n)=2^n-1-\sum_{k=2}^n F\left(\left\lfloor \dfrac{n}{k}\right\rfloor\right) \]

式子长得像杜教筛，复杂度 \(O(n^{3/4})\) 不太好过。

考虑设 \(f(d)\) 为 \(\gcd=d\) 的方案数，\(g(d)\) 为 \(d \mid \gcd\) 的方案数，则 \(g(d)=2^{\left\lfloor n/d\right\rfloor}-1\)，且有：

\[g(d)=\sum_{d\mid n} f(n) \]

根据莫比乌斯反演有：

\[f(d)=\sum_{d\mid n} \mu\left(\dfrac{n}{d}\right) g(n) \]

所以：

\[f(1)=\sum_{i=1}^n \mu(i)g(i)=\sum_{i=1}^n \mu(i)(2^{\left\lfloor n/i\right\rfloor}-1) \]

杜教筛预处理+整除分块即可，使用光速幂复杂度 \(O(n^{2/3})\)。

LOJ-6229 这是一道简单的数学题

把 \(j\) 的上下界改成 \([1,n]\)，处理一下 \(i=j\) 的情况即可。

简单反演得到：

\[\sum_{T=1}^n\sum_{d\mid T} \mu(d)d^2 S_1\left(\left\lfloor \dfrac{n}{d}\right\rfloor\right)^2 \]

\(S_1(x)\) 是 \(1\) 次自然数幂和。

于是要求 \(\sum_{d\mid n} \mu(d)d^2\) 的前缀和，不难发现这个函数是 \((\mu \cdot \mathrm{Id}_2)* \mathrm{I}\)，根据狄利克雷卷积的交换律以及结合律，可以得到 \((\mu \cdot \mathrm{Id}_2)*\mathrm{I}*\mathrm{Id}_2=(\mu \cdot \mathrm{Id}_2)*\mathrm{Id}_2*\mathrm{I}=\epsilon*\mathrm{I}=\mathrm{I}\)。

于是有：

\[S_f(n)=n-\sum_{i=2}^{n} i^2S_f\left(\left\lfloor \dfrac{n}{i}\right\rfloor\right) \]

杜教筛处理即可。

LOJ-6491 [XXOI 2018]简单的最大公约数

和上面的题差不多，先设 \(f(m)\) 表示值域 \([1,m]\)，\(n\) 个数 \(\gcd=1\) 的方案数，答案是 \(\sum_{k=1}^m k\times f\left(\left\lfloor \dfrac{m}{k}\right\rfloor\right)\)，最终求解用整除分块。

\[f(m)=m^n-\sum_{i=2}^m f\left(\left\lfloor \dfrac{m}{i}\right\rfloor\right) \]

直接算还是 \(O(n^{3/4})\)。

希望预处理一些 \(f\)。

依旧是莫比乌斯反演，把 \(f(m,k)\) 扩充到值域 \([1,m]\)，\(\gcd=k\) 的方案数，\(g(m,k)\) 定义为值域 \([1,m]\)，\(k\mid \gcd\) 的方案数，于是反演得到：

\[g(m,k)=\left\lfloor \dfrac{m}{k}\right\rfloor^{n} \]

\[f(m,k)=\sum_{k\mid m'} \mu\left(\dfrac{m'}{k}\right) \left\lfloor \dfrac{m}{m'}\right\rfloor^{n} \]

只关心 \(k=1\)，所以有：

\[f(m)=\sum_{k=1}^m \mu(k) \left\lfloor \dfrac{m}{k}\right\rfloor^{n} \]

这个直接求一行比较困难，考虑差分：

\[\begin{aligned} \Delta f(m)&=f(m)-f(m-1)\\ &=\sum_{k=1}^m \mu(k) \left(\left\lfloor \dfrac{m}{k}\right\rfloor^{n}-\left\lfloor \dfrac{m-1}{k}\right\rfloor^{n}\right) \end{aligned} \]

分析一下什么时候 \(\left\lfloor \dfrac{m}{k}\right\rfloor\neq \left\lfloor \dfrac{m-1}{k}\right\rfloor^{n}\)，显然一定是 \(k\mid m\)，即 \(m\) 恰好到了下一个块里。

于是这个预处理就是调和级数 \(O(n\log n)\) 的，由于 \(\mu\) 的性质，实际产生贡献的会更少。

这样大致处理 \(2\times 10^6\) 左右，再套类似杜教筛的东西就可以通过了。

另一个做法是使用欧拉反演，即利用 \(\varphi *\mathrm{I}=\mathrm{Id}\) 的性质，可以得到：

\[\begin{aligned} &\sum_{i_1=1}^m\sum_{i_2=1}^m\cdots\sum_{i_n=1}^m \gcd(i_1,i_2,\cdots,i_n)\\ =&\sum_{i_1=1}^m\sum_{i_2=1}^m\cdots\sum_{i_n=1}^m \sum_{d\mid \gcd(i_1,i_2,\cdots,i_n)} \varphi(d)\\ =&\sum_{d=1}^m \varphi(d) \left\lfloor\dfrac{m}{d}\right\rfloor^n \end{aligned} \]

杜教筛朴素计算即可。

PN 筛

Powerful Number

定义一个数 \(n\) 是 Powerful Number(PN) 当且仅当 \(n=\prod_{p\in \mathbf{P}} p_i^{c_i},c_i>1\)。

每个 PN 一定可以被唯一表示为 \(a^2b^3\) 的形式，次数为偶数的放在 \(a\) 部分，次数为奇数的将 \(3\) 次放在 \(b\) 部分，剩余放在 \(a\) 部分。

于是可以通过，，枚举 \(a\) 的值来计算 PN 的个数，大致是：

\[O\left(\sum_{i=1}^{\sqrt{n}}\sqrt[3]{\dfrac{n}{i^2}}\right)=O\left(\int_1^{\sqrt{n}} \sqrt[3]{\dfrac{n}{i^2}}\right)=O(\sqrt{n}) \]

所以可以通过 DFS 来得出所有 PN。

求积性函数前缀和

以模板题为例。

给定积性函数 \(f\)，求其前缀和。

考虑构造积性函数 \(g\)，满足 \(g(p)=f(p)\)，这里 \(g(p)=f(p)=p(p-1)\)，可以构造 \(g=\varphi\cdot\mathrm{Id}\)。

再找到积性函数 \(h\)，满足 \(f=g*h\)，由于 \(f(p)=g(1)h(p)+g(p)h(1)\)，积性函数 \(1\) 处点值一定为 \(1\)，所以 \(f(p)=h(p)+g(p)\)，即 \(h(p)=0\)，这样所有可以被质因子筛到的点值处都是 \(0\)，也就是所有非 PN 点值都是 \(0\)。

这样化简 \(f\) 前缀和的式子：

\[\begin{aligned} &\sum_{i=1}^n f(i)\\ =&\sum_{i=1}^n \sum_{j\mid i}g(i)h\left(\dfrac{i}{j}\right)\\ =&\sum_{i=1}^n h(i)S_g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)\\ =&\sum_{\substack{i=1\\ \text{i is PN}}}^n h(i)S_g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right) \end{aligned}\]

\(g\) 的前缀和可以用杜教筛求出（有更优秀的也可以），计算答案在 DFS 求出所有 PN 时进行，其中求 \(h\) 可以求出所有 \(h(p^c)\) 再累乘。

求 \(h(p^c)\) 最常规的办法是利用 \(f=g*h\)，移项得到 \(h(p^c)=f(p^c)-\sum_{i=0}^{c-1} h(p^i)g(p^{c-i})\)。

复杂度分析

求 \(g\) 前缀和复杂度认为是杜教筛复杂度 \(O(n^{2/3})\)。

由素数密度 \(\pi(n)=O\left(\dfrac{n}{\log n}\right)\) 知，只预处理 \(O(\sqrt{n})\) 的质数，暴力枚举每个 \(p^c\) 并 \(O(\log n)\) 计算 \(h\) 的值，复杂度是 \(O(\sqrt{n}\log n)\)，实际这个上界比较松。

于是得到大致是 \(O(n^{2/3})\) 的复杂度。

算法流程总结

用积性函数拟合出合适的 \(g\)。
构造快速求 \(g\) 前缀和的方法。
预处理出 \(h(p^c)\)。
DFS 出所有 PN 并计算答案。

例题

LOJ-6053 简单的函数

\(p\) 处点值是 \(p-1\)，除了 \(f(2)=3\)，先不考虑这一点的话拟合成 \(\varphi\) 是非常好的，在此基础上 \(\varphi(2)=1\)，所以将 \(2\) 的倍数处拟合成 \(3\varphi\)（肯定不是 \(\varphi+2\)吧）。

\[g(n)=\begin{cases}3\varphi(n)&2\mid n\\\varphi(n)&2\nmid n\end{cases} \]

把 \(\varphi\) 提出一个会好一点，顺便把系数也带出来：

\[l(n)=\begin{cases}\varphi(n)&2\mid n\\0&2\nmid n\end{cases} \]

于是 \(g(n)=\varphi(n)+2l(n)\)，也即 \(S_g(n)=S_\varphi(n)+2S_l(n)\)。

注意到 \(S_l(n)\) 有意义的 \(n\) 都是偶数，可以用一个 \(S(n)=\sum_{i=1}^n \varphi(2i)\) 来代替，即 \(S_l(n)=S\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right)\)。

把 \(\varphi(2n)\) 详写成关于 \(n\) 的：

\[\varphi(2n)=\begin{cases}2\varphi(n)&2\mid n\\\varphi(n)&2\nmid n\end{cases} \]

参照上面的化简方法，得到：

\[\varphi(2n)-\varphi(n)=\begin{cases}\varphi(n)&2\mid n\\0&2\nmid n\end{cases} \]

这个和 \(l\) 一模一样，这里当然再把 \(S_l\) 换成 \(S\)。

\[S(n)=S_\varphi(n)+S\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right) \]

放回最初的式子 \(S_g(n)=S_\varphi(n)+2S_h(n)=S_\varphi(n)+2S\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right)\)，这样一直把 \(S\) 展开，就是一个倍增的形式，单次计算是 \(O(\log n)\)，所求点值都在杜教筛射程范围内。

构造的另一函数 \(h\) 就是朴素的 \(O(\sqrt{n}\log n)\) 预处理。

根据 PN 的数量级和预处理的复杂度，总体仍是 \(O(n^{2/3})\)。

参考资料