參考文檔:

https://wenku.baidu.com/view/fbec9c63ba1aa8114431d9ac.html

假設$F(n)=\sum_{d|n}f(d)$,那么$f(n)=\sum_{d|n}μ(d)F(\frac{n}tvnlhlzrh9)$

假設$F(n)=\sum_{n|d}f(d)$,那么$f(n)=\sum_{n|d}μ(\fractvnlhlzrh9{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}μ(\fractvnlhlzrh9{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}tvnlhlzrh9)$

杜教篩：求$\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}^n\sum_{d|i}\phi(\frac{n}tvnlhlzrh9)*g(d)=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor \frac{n}tvnlhlzrh9 \rfloor}f(i)=\sum_{d=1}g(d)*S(\lfloor \frac{n}tvnlhlzrh9 \rfloor)$

$\sum_{i=1}^n(f*g)(i)=\sum_{d=1}^ng(d)*S(\lfloor \frac{n}tvnlhlzrh9 \rfloor)$

那么有$g(1)*S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^ng(d)*S(\lfloor \frac{n}tvnlhlzrh9 \rfloor)$

讓$g=I$(常函數),由于當$f=\mu$時，$\mu*I=\e$，那么$S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^nS(\lfloor \frac{n}tvnlhlzrh9 \rfloor)=1-\sum_{d=2}^nS(\lfloor \frac{n}tvnlhlzrh9 \rfloor)$

當$f=\phi$時，$\phi*I=id$,那么$S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^nS(\lfloor \frac{n}tvnlhlzrh9 \rfloor)=n*(n+1)/2-\sum_{d=2}^nS(\lfloor \frac{n}tvnlhlzrh9 \rfloor)$

復雜度$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}tvnlhlzrh9)+\sum_{i=1}^{ \lfloor \frac{m}tvnlhlzrh9 \rfloor}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}^n\mu(i)^2=\sum_{i=1}^{\sqrt(n)}\mu(i)*{\lfloor \frac{n}{i^2} \rfloor}$

$\sum_{d|n}\mu(d)^2*\mu(\frac{n}tvnlhlzrh9)=\sum_{d=1}^{\sqrt(n)}\mu(i)$

$\mu(lcm(i,j))=\mu(i)*\mu(j)*\mu(gcd(i,j))$