注意：这是个人学习笔记，如果有人因为某些原因点了进来并且要看一下，请一定谨慎地阅读，因为可能存在各种奇怪的错误，如果有人发现错误请指出谢谢！
1、积性函数：对于函数f(n)，若满足对任意互质的数字a,b，a*b=n且f(n)=f(a)f(b)，那么称函数f为积性函数。显然f(1)=1。
2、狄利克雷卷积：对于函数f,g,定义它们的卷积为$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$。
3、两个积性函数的狄利克雷卷积仍为积性函数。
证明：
设f,g的狄利克雷卷积为h，即$h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$,设n=a*b,a或b为1时显然成立，下面证明a和b均不为1
设$n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}...p_{m}^{\alpha _{m}}$,$a=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}...p_{k}^{\alpha _{k}}$,$b=p_{k+1}^{\alpha _{k+1}}p_{k+2}^{\alpha _{k+2}}...p_{m}^{\alpha _{m}}$
其中$m\geq 2,1\leq k\leq m-1$
$h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$
$h(a)=\sum_{d1|n}f(d1)g(\frac{a}{d1})$
$h(b)=\sum_{d2|n}f(d2)g(\frac{b}{d2})$
首先h(n)等号右侧有$\prod_{i=1}^{m}(\alpha _{i}+1)$项，h(a)等号右侧有$\prod_{i=1}^{k}(\alpha _{i}+1)$项,h(b)等号右侧有$\prod_{i=k+1}^{m}(\alpha _{i}+1)$项,，所以h(n)和h(a)h(b)的项数是一样的。
其次，对于h(n)右侧的每一项，设某一项为f(x)g(y)，
$x=p_{1}^{\beta _{1}}p_{2}^{\beta _{2}}...p_{m}^{\beta _{m}}$,
$y=p_{1}^{\gamma _{1}}p_{2}^{\gamma _{2}}...p_{m}^{\gamma _{m}}$,
一定存在$X=p_{1}^{\beta _{1}+\gamma _{1}}p_{2}^{\beta _{2}+\gamma _{2}}...p_{k}^{\beta _{k}+\gamma _{k}},Y=p_{k+1}^{\beta _{k+1}+\gamma _{k+1}}p_{k+2}^{\beta _{k+2}+\gamma _{k+2}}...p_{m}^{\beta _{m}+\gamma _{m}}$，使得f(X)是h(a)右侧的项，g(Y)是h(b)右侧的项，由于f,g都是积性函数，那么f(X)g(Y)=f(x)g(y)。
因此，h(n)=h(a)h(b)。
简单讲就是两边项数相等，对于左边的每一项又都能在右边找到对应相等的项
（可能用到这样一点：如果a,b互质，则a的任意因子与b的任意因子间也互质）
4、欧拉函数是积性函数。
设$n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}...p_{m}^{\alpha _{m}}$,$a=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}...p_{k}^{\alpha _{k}}$,$b=p_{k+1}^{\alpha _{k+1}}p_{k+2}^{\alpha _{k+2}}...p_{m}^{\alpha _{m}}$,
那么$\varphi (n)=n\prod_{i=1}^{m}(1-\frac{1}{p_{i}}),
\varphi (a)=a\prod_{i=1}^{k}(1-\frac{1}{p_{i}})$,
$\varphi (b)=b\prod_{i=k+1}^{m}(1-\frac{1}{p_{i}})$,
由于n=ab，显然$\varphi (n)=\varphi (a)\varphi (b)$
5、莫比乌斯函数($\mu$)是积性函数。由莫比乌斯函数的定义，分1，-1，0讨论就好。
6、莫比乌斯反演：对于函数f(n)和F(n)，若$F(n)=\sum_{d|n}f(d)$，那么$f(n)=\sum_{d|n}\mu (d)F(\frac{n}{d})$。
·积性函数
定义在正整数集上的函数$f(n)$（称为算术函数），若$\text g \text c \text d(a,b)=1$时有$f(a)f(b)=f(ab)$，则$f(x)$称为积性函数。
一个显然的性质：（非恒等于零的）积性函数$f(n)$必然满足$f(1)=1$。
定义逐点加法$(f+g)(x)=f(x)+g(x),逐点乘法(f\cdot g)(x)=f(x)g(x)$。
一个比较显然的性质：若$f,g$均为积性函数，则$f\cdot g$也是积性函数。
积性函数的求值：$n=\prod p_i^{\alpha_i}$，则$f(n)=\prod f(p_i^{\alpha_i})$，所以只要解决$n=p^\alpha$时$f(n)$的值即可。
例如：
恒为1的常函数$1(n)=1$，
恒等函数$\text{id}(n)=n$，
单位函数$\epsilon(n)=[n==1]$，（这三个都是显然为积性）
欧拉函数$\varphi(n)$ （只要证两个集合相等就能证明积性）
莫比乌斯函数$\mu(n)$ （由定义也是显然的）
·Dirichlet卷积
对两个算术函数$f,g$，定义其Dirichlet卷积为新函数$f*g$，满足$(f*g)(n)=\sum_{d|n}{f(d)g(n/d)}$。
一些性质：
交换律$f*g=g*f$,
结合律$(f*g)*h=f*(g*h)$,
单位元$f*\epsilon=f$,
对逐点加法的分配律$f*(g+h)=f*g+f*h$
重要性质：若$f,g$均为积性函数，则$f*g$也是积性函数。（展开式子即可证明）
补一条：若g(n)与(f*g)(n)都是积性函数，则f(n)亦为积性函数。特别地，当F=f*μ为积性函数时，f(n)亦为积性函数。
https://baike.baidu.com/item/%E7%8B%84%E5%88%A9%E5%85%8B%E9%9B%B7%E4%B9%98%E7%A7%AF
不太会证（但是可以从正向证的过程去理解）
说起来，那个”积性函数的前缀和也是积性函数“好像是假的。。(如果没有什么特别解释的话）
$n$的约数个数$d(n)$可以写成$d(n)=(1*1)(n)$；约数和$\sigma(n)$可以写成$\sigma(n)=(1*\text{id})(n)$，由上面的性质可知这两个函数均是积性函数。
重要性质：$\sum_{d|n}{\mu(d)}=[n==1]$，即$1*\mu=\epsilon$。（可用二项式定理证明）
重要性质：$\sum_{d|n}{\varphi(d)}=n$，即$1*\varphi=\text{id}$。（n是质数时显然成立，再由积性得证）
这个式子有一个变形：$\varphi(n)=\sum_{d|n}\mu(d)\frac{n}{d}$，即$\varphi=\mu*id$
证明：
$\varphi(n)=\sum_{i=1}^n[(i,n)=1]$
$=\sum_{i=1}^n\sum_{d|(i,n)}\mu(d)$
$=\sum_{i=1}^n\sum_{d=1}^n\mu(d)[d|i][d|n]$
$=\sum_{d|n}\mu(d)\frac{n}{d}$
参考：https://www.cnblogs.com/Troywar/p/7599875.html
额，好吧，其实以上式子也可以由莫比乌斯反演证明
那么，两边同时狄利克雷卷积上一个$1$，就得到了$1*\varphi=1*\mu*id=id$
好像也有别的证法。。好像这一堆式子（包括反演公式）都可以互推。。。
·O(nlgn)预处理Dirichlet卷积
若已知$f(i),g(i),i=1,2,\dots,n$的值，则可以在O(nlgn)时间内计算出$(f*g)(i),i=1,2,\dots,n$。
int f[MAXN],g[MAXN],h[MAXN]={0};
void calc(int n)
{
for (int i=1;i*i<=n;i++)
for (int j=i;i*j<=n;j++)
if(j==i)h[i*j]+=f[i]*g[i];
else h[i*j]+=f[i]*g[j]+f[j]*g[i];
}
·线性筛O(n)预处理
int pr[MAXN],bo[MAXN]={0},tot=0;
void sieve(int n){
for (int i=2;i<=n;i++){
if(!bo[i])pr[++tot]=i;
for (int j=1;j<=tot && pr[j]*i<=n;j++){
bo[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
}
可以证明每个合数只会被其最小质因子筛去，因此复杂度为线性。
如果能够充分挖掘$f(n)$的性质，则可以用线性筛在O(n)时间内预处理$f(i),i=1,2,\dots,n$。
关键在于对下面三种情况分别进行处理：
1.$x$是质数，求$f(x)$
2.$p$是质数，$p\nmid x$，求$f(px)$
3.$p$是质数，$p\mid x$，求$f(px)$
第1种情况往往比较简单。如果能证明$f$是积性函数，则容易知道第2种情况是$f(px)=f(p)f(x)$，剩下只要解决第3种情况的递推就够了。
有时虽然$f$不是积性函数，但也能够通过分析其性质分别解决这三种情况（后面会举一些例子）。
回过头再看欧拉函数的线性筛
用到两个性质：
对于质数p，
当i%p!=0时，phi[i*p]=phi[i]*phi[p]=phi[i]*(p-1)（显然i与p互质，根据积性函数性质可得）
当i%p==0时，phi[i*p]=phi[i]*p
原因：显然i*p,i有着相同的一些质因子；那么在直接计算欧拉函数的那个式子里面，只有第一项(n)不同（一个是i*p,另一个是i），那么它们的欧拉函数值之间的商phi[i*p]/phi[i]=(i*p)/i=p
回过头看莫比乌斯反演
证明：当$F(n)=\sum_{d|n}f(n)$即$F=f*1$时，$f=f*1*\mu=F*\mu$
奇怪的东西：https://baike.baidu.com/item/%E7%8B%84%E5%88%A9%E5%85%8B%E9%9B%B7%E9%80%86（狄利克雷逆）
根据这个，好像狄利克雷卷积满足对于c(1)不等于0，如果a*c=b*c，那么a=b（？？？只是说好像)