参考文档:
https://wenku.baidu.com/view/fbec9c63ba1aa8114431d9ac.html
假设$F(n)=sum_{d|n}f(d)$,那么$f(n)=sum_{d|n}μ(d)F(frac{n}{d})$
假设$F(n)=sum_{n|d}f(d)$,那么$f(n)=sum_{n|d}μ(frac{d}{n})F(d)$
μ(d)即莫比乌斯系数，
$μ(d)=1(n==1)$
$μ(d)=(-1)^k,d=p1*p2*...*pk，p1，p2，pk$是互不相同的素数，否则μ(d)=0
$sum_{d|n}μ(d)=1(n==1)$
$sum_{d|n}μ(d)=0(n!=1)$
即[n==1] == $sum_{d|n}μ(d)$
积性函数：$f(x*y)=f(x)*f(y)$(x,y互质)
完全积性函数:$f(x*y)=f(x)*f(y)$(x,y任意整数)
莫比乌斯函数也是积性函数
重要用途:容斥
假设$f(n)$表示gcd=k的方案数,$F(n)$表示gcd=k的倍数的方案数,那么有$F(n)=sum_{n|d}f(d)$
有莫比乌斯反演,$f(n)=sum_{n|d}μ(frac{d}{n})F(d)$,再利用整除分块前缀和搞一搞就能优化到$sqrt{n}$
常见的数论函数
$I(n)=1$(常函数）
$mu(n)$(莫比乌斯函数)
$phi(n)$(欧拉函数)
$e(n)=[n==1]$(单位函数)
$id(n)=n$
$d(n)=(p_1+1)*...*(p_k+1),(n=a_1^{p_1}*...*a_k^{p_k})$约数个数函数
因为$sum_{d|n}mu(d)=[n==1]$,所以$I*mu=e$
因为$n=sum_{d|n}phi(d)$，所以$I*phi=id$
#狄利克雷卷积
定义：$(f*g)(n)=sum_{d|n}f(d)*g(frac{n}{d})$
杜教筛：求$sum_{i=1}^n mu(i)(1<=n<=1e10)$
设$S(n)=sum_{i=1}^n mu(i)$
由狄利克雷卷积
$sum_{i=1}^n(f*g)(i)=sum_{i=1}^nsum_{d|i}phi(frac{n}{d})*g(d)=sum_{d=1}^ng(d)sum_{i=1}^{lfloor frac{n}{d} floor}f(i)=sum_{d=1}g(d)*S(lfloor frac{n}{d} floor)$
$sum_{i=1}^n(f*g)(i)=sum_{d=1}^ng(d)*S(lfloor frac{n}{d} floor)$
那么有$g(1)*S(n)=sum_{i=1}^n(f*g)(i)-sum_{d=2}^ng(d)*S(lfloor frac{n}{d} floor)$
让$g=I$(常函数),由于当$f=mu$时，$mu*I=e$，那么$S(n)=sum_{i=1}^n(f*g)(i)-sum_{d=2}^nS(lfloor frac{n}{d} floor)=1-sum_{d=2}^nS(lfloor frac{n}{d} floor)$
当$f=phi$时，$phi*I=id$,那么$S(n)=sum_{i=1}^n(f*g)(i)-sum_{d=2}^nS(lfloor frac{n}{d} floor)=n*(n+1)/2-sum_{d=2}^nS(lfloor frac{n}{d} floor)$
复杂度$O(n^{frac{2}{3}})$,前$n^{frac{2}{3}}$预处理，后面的根据分块记忆化递推
板子题：https://www.cnblogs.com/acjiumeng/p/9523233.html
积性函数倍数和
$sum_{i=1}^mf(i*n)=-sum_{i=1}^mf(i*frac{n}{d})+sum_{i=1}^{ lfloor frac{m}{d} floor}f(i*n)$
$d(n*m)=sum_{i|n}sum_{j|m}[gcd(i,j)==1]$
欧拉函数性质:所有小于n和n互质的数的和为$frac{n*phi(n)}{2}$,即$sum_{i=1}^{n-1}i[(i,n)==1]=frac{n*phi(n)}{2}$
证明:gcd(n,i)=1,那么gcd(n,n-i)=1.反证法:假设gcd(n,n-i)=k,那么n-i%k=0,n%k=0,则i%k=0,那么gcd(n,i)=k,那么这些数成对出现,而且加起来是n
$sum_{i=1}^nmu(i)^2=sum_{i=1}^{sqrt(n)}mu(i)*{lfloor frac{n}{i^2} floor}$
$sum_{d|n}mu(d)^2*mu(frac{n}{d})=sum_{d=1}^{sqrt(n)}mu(i)$
$mu(lcm(i,j))=mu(i)*mu(j)*mu(gcd(i,j))$