会挖坑，好让复习的时候长脑子。
以下所有 \(p\) 都是质数，即 \(p\in\mathbb{P}\)，同时默认均为正整数。
Base
唯一分解定理（算术基本定理）：
\[\begin{align} \forall n>1,n=\prod\limits_{i=1}^k p_i^{t_i} \end{align} \]后面默认都分解了。
积性函数：
\[\begin{align} \forall x\perp y,f(xy)=f(x)f(y) \end{align} \]完全积性函数：
\[\begin{align} \forall x,y\in\N_+,f(xy)=f(x)f(y) \end{align} \]完全积性函数出现的比较少，不过积性函数也较好处理，可以线性筛。
经典的积性函数：
-
\(\varphi\)：欧拉函数。有性质 \(\varphi(n)=n\prod{\frac{p_k-1}{p_k}}\) 和 \(n=\sum\limits_{d\mid n}\varphi(d)\)。
第一个考虑 \(\varphi(p^t)\) 的取值，发现是 \(p^{t-1} (p-1)\) 就很好说明。
第二个考虑 \(\frac{1}{n},\frac{2}{n},\dots,\frac{n}{n}\) 这一串数的个数，化成最简分数来算。
-
\(\mu\)：莫比乌斯函数。原始定义是 \(\sum\limits_{i=1}^n\mu(i)=[n=1]\)。
根据定义可得:
-
\(\text{d}\) 与 \(\sigma\) 及 \(\sigma_k\)：约数个数函数 与 约数和函数 及 除数函数。
其实 \(\text{d}\) 就是 \(\sigma_0\)……
表述可以是：\(\sigma_k(n)=\sum\limits_{d\mid n}d^k\)。
一些比较牛逼的完全积性函数：
- \(\epsilon\)
，依夫瑟洛！：狄利克雷卷积下的单位元，\(\epsilon(n)=[n=1]\)。 - \(\text{I}\)：单位函数，\(\text{I}(n)=1\)。
- \(\text{Id}\) 与 \(\text{Id}_k\)：就是走个形式，\(\text{Id}_k(n)=n^k\)。
别的先不谈，考虑怎么算积性函数。
Sieve base
其实说筛之前应该先看一下积性函数的计算原理。
由于算术基本定理，任意数都可以表为若干个质数的次幂乘积。
因此我们只要分解 \(x\)，就可以根据积性函数的性质乘出 \(f(x)\)。
由于分解难，往往是 \(\mathcal{O}(\sqrt{n})\) 的复杂度，当然有一些随机算法能做到更优。
然而另一种思路是主动去凑 \(n\)，这在要求出 \(1\sim n\) 的 \(f\) 的值时就会更快。
这样就成了筛法。
埃筛 is too naive，看线性筛。
线性筛使得每个数字只被自己的最小质因子筛一次，过程如下：
Note: This is not pseudocode!
- If i is a prime
- Add i into the P
- For all pri in P
- Calc x=i*p
- if p is a divisor of i
* Calc x by p and i,then break
- else f(x)=f(i)*f(p)
关键步骤在 * 一句，我们需要根据 \(p\) 和 \(i\) 算出 \(x=ip\) 的值，而此时 \(i\) 中已经含有至少一个 \(p\)。
可以使用无脑做法：\(f(x)=f(\frac{i}{p^t})f(p^t)\)，显然可知 \(\frac{i}{p^t} \perp p^t\)，正确性有保障。
注意像 \(x=p^t\) 这样形式的情况要特别算。
这个基本就是线性筛积性函数的普适做法，感觉其实非常地简单但我当初就是听不懂。
Dirichlet Convolution
即狄利克雷卷积（以下简称卷积），定义如下：
若 \(h=f*g\)，则
\[h(n)=\sum\limits_{d\mid n}f(d)g(\frac{n}{d})=\sum\limits_{d\mid n}g(d)f(\frac{n}{d}) \]卷积满足交换律：\(f*g=g*f\)。
同时满足结合律：\((f*g)*h=f*(g*h)\)。
一些常见的卷积：
- \(\epsilon*f=f\)
- \(\text{I}*\mu=\epsilon\)
- \(\text{Id}_k*\text{I}=\sigma_k\)
- \(\text{I}*\varphi=\text{Id}\)
- \(\text{Id}*\varphi=\mu\)
上面这些都可以拆式子得到。
比较重要的，卷积结合点乘的特殊规律：
\((f\cdot g)*(f\cdot h)=f\cdot(g*h)\)，要求 \(f\) 是完全积性函数。
考虑证明：
\[\begin{align} (f\cdot g)*(f\cdot h)(n) &=\sum\limits_{d\mid n} (f\cdot g)(d)(f\cdot h)(\frac{n}{d}) \\ &=\sum\limits_{d\mid n} f(d)f(\frac{n}{d})g(d)h(\frac{n}{d}) \\ &=\sum\limits_{d\mid n} f(n)g(d)h(\frac{n}{d}) \\ &=f(n)\sum\limits_{d\mid n} g(d)h(\frac{n}{d}) \\ &=f(n)\cdot(g*h)(n) \end{align} \]显然成立。
Sqrt Decomposition
现在补充这个 trick。
标签：frac,筛法,limits,数论,text,函数,积性,sum,小记 From： https://www.cnblogs.com/LQ636721/p/17763542.html