Mobius_and_Dirichlet

Orz _rqy , An_account , negiizhao , Elegia, Wkywkywky.

在这里添加一点杂乱的东西，这一块以后需要大修。。。

关于 $\operatorname{lcm}$ 卷积：

$$
h ( n ) = \sum _ { i = 1 } ^ { n } \sum _ { j = 1 } ^ { n } f ( i ) g ( j ) [ \operatorname {lcm} ( i , j ) = n ]
$$

这个卷积等价于：

$$
h \ast \mathbf{1} = ( f \ast \mathbf { 1 } ) \cdot ( g \ast \mathbf{1} )
$$

实际上只要知道：

$$ [\operatorname{lcm} ( i ,j ) \mid n ] = [ i \mid n ] [ j \mid n ]$$

就可以推导了。。。

这里 $\gcd$ 卷积没有太大的推导价值。。。因为大部分情况是会产生无限求和的状况的。。。

然后再说一点可能大家都知道不过没有那么敏感的东西，一个数论函数的 $\mu$ 变换和 $\zeta$ 变换都是可以 $O( n \ln n )$ 求出前 $n$ 个函数值的（埃氏筛）。。。

顺便补充一个 Wky 大师送我的 rqy 题。。。

对于 $ n = \prod _ { i = 1 } ^ { k } p _ i ^ { c _ i }$，有关于 $\max c _ i$ 和 $\min c _ i$ 的二元函数 $f ( n )$。

我们存在 $O(\sqrt{n} \log n)$ 的方法求出 $\sum _ { i = 1 } ^ { n } f ( i )$。

这个方法用到了一点 PN 筛的技巧，同时还有一个容斥（我根本想不到）。

但介于这个题本身属于去年省选计划的题，实际上这样公开不太好（虽然这是一道团队公开题并且所有人都能提交）。。。

不过像我这种没几个人知道的 OIer 把这玩意贴到博客里也没什么问题吧。。。

可能会存在狄利克雷生成函数能做而贝尔级数做不了的东西（只要出现一个非积性数论函数，并且这个东西需要有神奇的方法求值）（我会考虑在之后尝试造一道这样的入门题）。。。

会补充到下面的（咕咕咕）。

还有一些是我想继续学习后补充到下面的，实际上就是几个高级筛法，但是复杂度会比较优秀。

有所耳闻的就是 PN 筛，Min-25 筛，zzt 筛。。。

把 negiizhao 的博客贴在 这里 备忘一下。

实话说数论这一块的水确实很深。。。光是莫反这一块能挖掘的东西就不少。。。

数学的话更不用说了，我感觉我现在快要在数学之海里溺死了。。。

一、基本定义

我们先定义数论函数：定义域为正整数，值域为一个数集的函数。

定义两个数论函数的狄利克雷卷积：

• 若 $t=f\ast g$，则 $t(n)=\sum_{i\mid n}f(i)g\left(\dfrac{n}{i}\right)$。

狄利克雷卷积是满足交换律和结合律的。

我们再补充一个分配律：$(f+g)\ast h=f\ast h+g\ast h$（这个很显然啊）。

以及一个逆元的求法：

• 对于每个 $f(1)\not = 0$ 的函数 $f$，都有 $g$ 使 $f*g=\varepsilon$。

• 定义 $g(n)=\dfrac{1}{f(1)}\left([n=1]-\sum_{i\mid n,i\not =1}f(i)g\left(\dfrac{n}{i}\right)\right)$。

• 易知：$\sum_{i\mid n}f(i)g\left(\dfrac{n}{i}\right)=f(1)g(n)+\sum_{i\mid n,i\not = 1}f(i)g\left(\dfrac{n}{i}\right)=[n=1]$。

补充结论：

1. 两个积性函数的狄利克雷卷积是积性函数。

   证明：若 $n\bot m$，且 $a\mid n$，$b\mid m$，则 $a\bot b$，此时：

   $$\begin{aligned}
   t(nm)&=\sum_{d\mid nm}f(d)g\left(\dfrac{nm}{d}\right)
   \\
   &= \sum_{ab\mid nm}f(ab)g\left(\dfrac{nm}{ab}\right)
   \\
   &= \sum_{ab\mid nm} f(a)g\left(\dfrac{n}{a}\right)f(b)g\left(\dfrac{m}{b}\right)
   \\
   &= \left(\sum_{a\mid n}f(a)g\left(\dfrac{n}{a}\right)\right)\left(\sum_{b\mid n}f(b)g\left(\dfrac{m}{b}\right)\right)
   \\
   &= t(n)t(m) & \square
   \end{aligned}$$

2. 积性函数的逆是积性函数（不考虑 $f(1)=0$）。

   证明：考虑对 $nm$ 的大小进行归纳。

   • 若 $nm=1$，则 $g(1)=1$，结论成立

   • 假设 $nm>1$，当 $n’m’<nm$ 时有 $g(n’m’)=g(n’)g(m’)$，欲证 $nm$ 时满足命题：

     $$\begin{aligned}
     g(nm)&=-\sum_{d\mid nm,d\ne 1}f(d)g\left(\dfrac{nm}{d}\right)
     \\
     &= -\sum_{a\mid n,b\mid m,ab\ne 1}f(a)f(b)g\left(\dfrac{n}{a}\right)g\left(\dfrac{m}{b}\right)
     \\
     &= f(1)f(1)g(n)g(m)-\sum_{a\mid n,b\mid m}f(a)f(b)g\left(\dfrac{n}{a}\right)g\left(\dfrac{m}{b}\right)
     \\
     &= g(n)g(m)-\left(\sum_{a\mid n}f(a)g\left(\dfrac{n}{a}\right)\right)\left(\sum_{b\mid m}f(b)g\left(\dfrac{m}{b}\right)\right)
     \\
     &= g(n)g(m)-\varepsilon(n)\varepsilon(m)
     \\
     &= g(n)g(m)
     \end{aligned}$$

     这里 $\dfrac{nm}{ab}<nm$ 可运用归纳条件。

   $\mathcal{Q.E.D.}$

二、符号及常用结论

1. 常用的几个符号：

   $\varepsilon$，这个函数是单位元，具体来说，除了 $\varepsilon(1)=1$，其余都为 0。（读法：epsilon，完全积性）

   $\mathbf{id}$，字面意思就是 $\mathbf{id}(n)=n$。（完全积性）

   $\sigma_k$，这个叫做除数函数，具体来说它是 $\sigma_k(n)=\sum_{d\mid n}d^k$。（读法：sigma，积性）

   $\mathbf{1}$，它就是黎曼函数。具体来说就是 $\mathbf{1}(n)=\zeta(n)=1$。（读法：zeta，完全积性）

   $\varphi$ 和 $\mu$ 我就不多介绍了。

2. 常用结论：

   • 莫比乌斯反演：

     $$[n=1]=\sum_{d\mid n}\mu(d)$$

     写成狄利克雷卷积就是：

     $$\varepsilon=1\ast\mu$$

   • 欧拉反演（然而没有这个名字，暂且可以这么称呼）：

     $$n=\sum_{d\mid n}\varphi(d)$$

     写成狄利克雷卷积就是：

     $$\mathbf{id}=1\ast \varphi$$

     其逆即为：

     $$\mathbf{id}*\mu=\varphi$$

   • 约数函数有关卷积：

     $$\sigma_0=\mathbf{1}*\mathbf{1}$$

     $$\sigma=\mathbf{id}*\mathbf{1}$$

     $$\sigma _ k = \mathbf{id} ^ k \ast \mathbf{1}$$

     以及一个：

     $$\sigma _ 0 (xy)=\sum _ {i\mid x}\sum _ {j\mid y} [\gcd (i,j)=1] $$

     这个结论的扩展：

     $$\sigma _ 0(xyz)=\sum_{i\mid x}\sum_{j\mid y}\sum_{k\mid z}[\gcd(i,j)=1][\gcd(j,k)=1][\gcd(i,k)=1]$$

三、积性函数求法

通过线性筛求积性函数，一般有两种方法：

1. 分类讨论这个东西：

   • $f(1)=1$。
   • $n\in \mathcal{P},f(n)$，这里 $\mathcal{P}$ 指质数集（并不知道初等数论中那个炫酷的符号是怎么打出来的）。
   • $p\mid n,p^2 \nmid n,f(n)=f\left(n/p\right)f(p)$
   • $p\mid n,p^2\mid n,f(n)$，这里一般不同情况不同分析。
   • 经典的例子有一般的 $\mu$ 和 $\varphi$ 的求法。

2. 先算出 $f$ 在素数幂的取值，对于每个 $n$ 求出其最小质因数 $p_k$ 及 其次数 $c_k$，直接 $f(n)=f(p_k^{c_k})f\left(n/{p_k^{c_k}}\right)$ 算就完了。这个次数可以递推求。

   当然素数幂处的取值也不一定很好求，反正不管怎样是要动脑子的。

3. （从 EI 的知乎专栏看到的）现在我们来谈一谈一种特殊的情况 $h=f*g$，其中 $f$ 和 $g$ 都是积性函数。

   很容易知道 $h$ 是积性函数。那么同理我们可以按照上面的方法 2 求取。

   那么很显然我们需要知道这个 $h$ 在 $p^k$ 的取值。

   容易知道：

   $$h(p^k)=\sum_{d=0}^{k}f(p^d)g(p^{k-d})$$

   那么我们在 $p^k$ 处计算 $h$ 需要 $\Theta(k)$ 的复杂度。

   这一块的复杂度分析就是 EI 专栏的精华（但也是最傻的/tx）。

   我们考虑枚举 $p$ 的指数 $k$，则 $k\le \log_2 n$。

   若我们指定 $k$，则使 $p^k\le n$ 的 $p$ 只有 $\pi(\lfloor \sqrt[x]{n}\rfloor)$ 个。

   因此这个复杂度：

   $$\begin{aligned}
   T(n)&=O\left(\sum_{x=1}^{\log_2 n} x\pi(\lfloor \sqrt[x]{n}\rfloor)\right)
   \\
   &= O\left(\sum_{x=1}^{\log_2 n}\dfrac{x\sqrt[x]{n}}{\ln \sqrt[x]{n}}\right)
   \\
   &= O\left(\dfrac{1}{\ln n}\sum_{x=1}^{\log_2 n}x^2\sqrt[x]{n}\right)
   \end{aligned}$$

   现在尝试寻找 $x^2\sqrt[x]{n}$ 的极值：

   $$\dfrac{\delta}{\delta x}x^2\sqrt[x]{n}=\sqrt[x]{n}(2x-\ln n)$$

   可知原函数单峰下凸，在 $x=1$ 时得 $n$。

   用最大值作界得到：

   $$T(n)\le \dfrac{\log_2 n}{\ln n}n=O(n)$$

   当然，数学明珠上的皇冠 Wky 大师直接给了一种更简明的方法：

   因为对于 $k=1$，一共有 $\pi(n)$ 个 $p$。

   对于每个 $k\in [2,\log_2 n]$，最多只有 $\pi(\sqrt[k]{n})<\sqrt[k]{n}$ 个 $p$。

   那么 $n$ 以内 $p^k$ 的个数就是 $O(\pi(n)+\sqrt{n}\log_2 n)=O\left(\dfrac{n}{\ln n}\right)$（数量级可以通过相除比较）。

   那么总的计算复杂度 $T(n)=O\left(\dfrac{n\log_2 n}{\ln n}\right)=O(n)$。

四、贝尔级数

这一块我也不太明白，也不怎么会用。

可以说是狄利克雷生成函数的一个较好替代品（看起来就要简洁许多），以至于我现在还不会狄利克雷生成函数。。。

讲解这个的主要是 rqy 和 cmd 的博客。

定义积性函数 $f$ 模 $p$ 的贝尔级数为：

$$f_p(x)=\sum_{i=0}^{\infty}f(p^i)x^i$$

这样的话根据积性函数的性质，狄利克雷卷积就变成了一般卷积：

$$(f\ast g)_p(x)=f_p(x)g_p(x)$$

加法形式也是有意义的，但是不是对应 $(f+g)$，这点请一定要注意：

$$h_p(x)=f_p(x)+g_p(x)$$

至于这玩意是什么，我只能最简单的解释一下，在素数幂处为两者函数值相加，其他数值处满足积性，这样的一个函数。减法当然也是同理。

求逆的话非常简单，若 $f\ast g=\varepsilon$，则：

$$f_p(x)g_p(x)=1$$

虽然有这种有意义的运算，然而狄利克雷卷积上却没有除法（雾），所以一般写法就类似于 $1=\mathbf{id}\ast \varphi^{-1}$ 这样子算了。

常见的封闭形式：

1. $\varepsilon_p(x)=1$

2. $\zeta_p(x)=\dfrac{1}{1-x}$

3. $ \mathbf {id} ^k _ p (x)=\dfrac{1}{1-p^kx}$

4. $\mu _ p(x)=1-x$，$(\mu\cdot\mu)_p(x)=1+x$

5. $\sigma _ {0p}(x)=\dfrac{1}{(1-x)^2}$

6. $\varphi_p(x)=\dfrac{1-x}{1-px}$

7. $(\mathbf{id}\cdot \mu)_p(x)=1-px$

想要推导出来就仔细想一想 $f(p^x)$ 等于什么，变成一个正常的 OGF，然后就会推了。

实在不会直接推导可以利用上面你已经理解的结论和自己知道的卷积来推导，比如 $\varphi _ p(x)=\mu _ p(x)\mathbf{id_p}(x)$。

或者说理解一下这个意义。。。我也没什么好方法。。。

点乘的话就是对应 $x^i$ 的系数相乘即可，很好理解。可惜没有什么贝尔级数上的初等运算可以对应。

一种特殊的点乘是数论函数 $f$ 点乘上 $\mathbf{id} ^ k $，这种情况下我们是可以求出其贝尔级数的：

$$
(f\cdot \mathbf{id} ^ k)_ p(x)=\sum_{i=0}^{\infty}f(p^i)p^{ki}x^{i}=\sum_{i=0}^{\infty}f(p^i)(p^kx)^i
$$

这个时候将 $p^kx$ 视作整体，代入 $f_p(x)$ 就好了。

比如：$(\varphi\cdot \mathbf{id} ^ 2)_p(x)=\dfrac{1-p^2x}{1-p^3x}$。

然后 P3768 简单的数学题 就可以做了。

有关这个的习题似乎很难找（？）。

所以我自己造了一道：U214268 不老不死的竹林引路人。或许用狄利克雷生成函数会更简洁，但我不会。

或者去看 rqy 博客里的那道奇怪的题目（显然会比这一题难处理一些）。

五、技巧总结

1. 推式子，我只会：

   公式瞎套，换序求和，换元乱搞，创造互质（构造 $[\gcd(x,y)=1]$），函数积性，函数求逆，提项合并，当场躺平。

   不怕出事可以从一些底层意义上面自己创造一些式子。

2. 关于如何理解莫比乌斯反演加速计算的本质：

   莫比乌斯反演的一种本质是数论容斥，实际上这个东西对加速计算本身没有什么帮助。

   真正加速计算的有两个：换序求和与数论分块。

   数论分块的加速效果想必不需要我多说。

   换序求和的加速实际上就是实现了对容斥集合的较优划分。

3. 关于数论分块被使用的原因：

   题目里有 $\gcd$，一般很容易扯到数论分块。

   原因就是 $x\mid\gcd(i,j)\Leftrightarrow x\mid i,x\mid j$。于是就能涉及到整除，从而牵扯到数论分块。

4. 定义运算 $\cdot$，表示 $(f\cdot g)(n)=f(n)g(n)$。

   很显然 $\mathbf{1}=\zeta$ 是单位元啊。

   若 $f$ 是完全积性的，有性质：

   $$(f\cdot g)\ast (f\cdot h)=f\cdot(g\ast h)$$

   除此我们一般的处理方法就是把它展开成一般的求和形式，然后使用普通的数学技巧化简。

   主要是用在杜教筛里的。

六、入门教程（应用）

以上都是一些比较结论性的东西。

想要训练的话可以跟着下面的入门。。。

题面自己搜。

建议初学者做例题的时候可以适当利用题解，熟练掌握例题中的基本思想，我保证在掌握了对应例题后练习题可以完全独立做出。

如果只是想要掌握基础的话，将例题和对应练习做掉即可，后面的 ABC 组练习题就可以不做，这些题目的主要目的是为了巩固。

A 组是基础题，难度和例题的对应练习保持一致，觉得 Trivial 可以直接跳过。

B 组放了一些稍微上了点难度的题，但总体来说仍然不难，想要巩固的话可以优先做这一组的题目。

C 组放了一些我自己觉得比较毒瘤的题，供想要继续深入的同学探究。。。

虽然笔者又加入了不少题目，但实际上难度上仍然不高，而且基本都是纯推式子题，只能帮助读者了解基础，更加高明的应用欠缺很多（我也无能为力）。

---

必备技能：UVA11526 H(n)

这里就是数论分块的基本内容。

练习：P2261 [CQOI2007]余数求和

• 希望这个题能让读者明白一个转化套路，就是想办法往 $\sum_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor$ 上去靠，然后用数论分块

---

接下来正式进入莫比乌斯反演：

例一：P3455 [POI2007]ZAP-Queries

• 这个题出现了几个常用技巧
• 一个是转化出条件 $[\gcd(i,j)=1]$
• 另一个就是把 $[\gcd(i,j)=1]$ 这个条件换成 $\sum_{d\mid \gcd(i,j)}\mu(d)$
• 最后一个就是换序求和（这个是最重要的）
• 区别于一般的反演做法，这种方法可能更适合入门
• 想要做题的话掌握这种技巧就足够了

练习一：P2522 [HAOI2011]Problem b

• 和上面的题其实一样
• 这里用到了容斥
• 希望读者能够熟悉一下上面的推导

---

例二：P2257 YY的GCD

• 这题需要的技巧是换元
• 形象的来说，我们设了一个 $T=kd$，然后让枚举的条件通过整除限制地更紧
• 通过这个方式来优化我们的复杂度

练习二：P2398 GCD SUM

• 希望读者熟悉一下刚才的技巧
• 同时希望读者提升观察能力，熟练运用常用结论
• 这里的欧拉反演（随便起的名字，实际上就是 $\mathbf{id}=\mathbf{1}\ast \varphi$）技巧一定要掌握

---

例三：P3327 [SDOI2015]约数个数和

• 需要用到上面的某个结论
• 只要看推导的式子就够了，杜教筛后面会讲（虽然这个题也没必要杜教筛）
• 没有什么典型性，希望读者能知道数论题的有些结论是背不到的

---

例四：P4318 完全平方数

• 我们结合了二分答案的技巧
• 主要是这个是否含平方因子与 $\mu^2$ 之间的转化

---

例五：P4213 【模板】杜教筛（Sum）

• 这里我们来讲一个常用的杜教筛
• 它的功用是帮助我们更快地求出数论函数的前缀和
• 应该说是必备技能

练习五：P3768 简单的数学题

• 比较简单的杜教筛题目
• 基本上就是构造一下就会做了（或者应用贝尔级数/狄利克雷生成函数的技巧）

---

例六：P3704 [SDOI2017]数字表格

• 并不是很难的题目
• 处理 $\prod$ 的技巧

大概把这些题目看完，对莫比乌斯反演类的题目，尤其是有关于 $\gcd$ 的题目会有基本的处理思想和技巧。

---

练习题 A 组：

1. P2260 [清华集训2012]模积和

   • 很简单的容斥
   • 数论分块练习

2. P1390 公约数的和

   • 欧拉反演练习
   • 简单容斥

3. P2424 约数和

   • 约数函数有关卷积的应用

4. P2158 [SDOI2008] 仪仗队

   • 先想办法找到要推的式子
   • 如果不会可以从互质切入

---

练习题 B 组：

1. P1447 [NOI2010] 能量采集

   • 上面题目的强化
   • 似乎也不难

2. P1829 [国家集训队]Crash的数字表格 / JZPTAB

   • 虽然可能不太适合做杜教筛的练习题（数据并没有卡死用杜教筛）
   • 希望读者就算不会杜教筛的方法做这道题也要会最基本的那个线性做法

3. U214268 不老不死的竹林引路人

   • 自己造的题目
   • 需要贝尔级数（知道这个这题就太简单了。。。）
   • 剩下就是简单的杜教筛模板
   • 高级筛法我不会

4. P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题

   • 把式子推完就要做大模拟了
   • 请一定要耐心。。。

5. P1587 [NOI2016] 循环之美

   • 一个按照素数幂分解 DFS 的小方法
   • 据说很像 Min_25 筛

---

练习题 C 组：

1. P4619 [SDOI2018]旧试题

   • 前面某道题目的扩展

2. P5572 [CmdOI2019]简单的数论题

3. P4240 毒瘤之神的考验

七、附录

$\LaTeX$ 使用表：

1. \mathbf{id} ^ 2 $\rightarrow \mathbf{id} ^ 2$

2. \zeta $\rightarrow \zeta$

3. \sigma _ 0 $\rightarrow \sigma _ 0$

4. \varphi $\rightarrow \varphi$

5. \varepsilon $\rightarrow \varepsilon$

6. \sqrt[x]{n} $\rightarrow \sqrt[x]{n}$

入门教程就到这里。

以上是一名平凡的 OIer 无私的馈赠。衷心希望想要入门数论求和类题目的人能够有所收获。

很可惜笔者题量太少，对数学的悟性也不高，只能写到这里了。