迪利克雷卷积

定义:$f(n),g(n)是两个积性函数$
$$(f*g)(n)=\sum_{d|n}f(d)·g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})·g(d)$$
性质:

1.交换律：$f*g=g*f$

2.结合律：$(f*g)*h=f*(g*h)$

3.分配律：$(f+g)*h=f*h=g*h$

常用函数

1.元函数： $\xi(n)=[n=1]$

2.常数函数：$1(n)=1$

3.恒等函数：$id(n)=n$

4.欧拉函数：$\varphi(n)=\sum_{i=1}^{n}[gcd(i,n)=1]$

性质：$\sum_{d|n}{\varphi(d)}=n$

5.莫比乌斯函数：
$\mu(n)= \begin{cases} 1 \quad n=1\\ 0 \quad n包含相同质因子\\ (-1)^s \quad n=p_1p_2…p_s \\ \end{cases}$

性质：$\sum_{d|n}\mu(d)=[n=1]$

6.莫比乌斯函数与欧拉函数的联系：
$$\sum_{d|n}\mu(d)\frac{n}{d}=\varphi(n)$$

常用卷积关系

1.$\sum_{d|n}\mu(d)=[n=1] \quad \Longleftrightarrow \quad u*1=\xi$

2.$\sum_{d|n}\varphi(d)=n \quad \Longleftrightarrow \quad \varphi*1=id$

3.$\sum_{d|n}\mu(d)·\frac{n}{d}=n \quad \Longleftrightarrow \quad u*id=\varphi$

4.$f*\xi=f$

5.$f*1\not=f$

6.$f*u*1=f$

证明

$(\mu*1)(n)=\sum_{d|n}\mu(d)·1(\frac{n}{d})=\sum_{d|n}\mu(d)=[n=1]=\xi(n)$

$(\varphi*1)(n)=\sum_{d|n}\varphi(d)·1(\frac{n}{d})=\sum_{d|n}\varphi(d)=[n=1]=id(n)$

$(\mu*id)(n)=\sum_{d|n}\mu(d)·id(\frac{n}{d})=\sum_{d|n}\mu(d)·\frac{n}{d}=\varphi(n)$

$(f*\xi)(n)=\sum_{d|n}f(d)·\xi(\frac{n}{d})=\sum_{d|n}f(d)·[\frac{n}{d}=1]=f(n)$

$(f*1)(n)=\sum_{d|n}f(d)·1(\frac{n}{d})=\sum_{d|n}f(d)$

$(f*u*1)(n)=(f*(u*1)(n))(n)=(f*\xi)(n)=f(n)$

杜教筛原理

用途：在低于线性时间里，高效率求一些积性函数的前缀和

原理：整除分块+迪利克雷卷积+线性筛

公式: $$g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^n{g(i)S(\lfloor{\frac {n}{i}\rfloor})}$$

推导:$\sum_{i=1}^n(f*g)(i)$

$=\sum_{i=1}^{n}\sum_{d|i}f(\frac{i}{d})g(d)=\sum_{i=1}^n\sum_{d=1}^n[d|i]f(\frac{i}{d})g(d)$

$=\sum_{d=1}^{n}\sum_{i=1}^{n}[d|i]f(\frac{i}{d})g(d)=\sum_{d=1}^{n}\sum_{id=1}^n[d|id]f(\frac{id}{d})g(d)$

$=\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}f(i)g(d)=\sum_{d=1}^{n}g(d)S(\frac{n}{d})$
$=g(1)S(n)+\sum_{d=2}^{n}g(d)S(\frac{n}{d})$

具体做法：

$1. \quad 使用线性筛预处理出n较小时的s(n)来剪枝$

$2. \quad 使用哈希表来做记忆化剪枝$

$3. \quad 使用整除分块做递归$

时间复杂度：$O(n^\frac {2}{3})$

杜教筛模板

以该题为例:
$$求s(n)=\sum_{i=1}^{n}\varphi(i)$$
解:
因为
$\varphi*1=id,所以f=\varphi,g=1,f*g=id$

$s(n)=\sum_{i=1}^{n}id(i)-\sum_{i=2}^{n}1(d)s(\frac{n}{i})$

$=\sum_{i=1}^{n}i-\sum_{i=2}^{n}s({\frac{n}{i}})=\frac{n(n+1)}{2}-\sum_{i=1}^{n}s(\frac{n}{i})$

const int N=2e5+10;
// 线性筛所需
bool vis[N];
vector<ll> pri;
// 所需处理的函数
ll mu[N],phi[N];
map<ll,ll> mp_phi;
// 线性筛初始化
void init(){
    phi[1]=1;  // n=1时的函数取值
    for(int i=2;i<N;i++) {
        if(!vis[i]) {
            pri.push_back(i);
            phi[i]=i-1; //处理n为素数时的函数取值
        }
        for(int j=0;1ll*i*pri[j]<N;j++) {
            vis[i*pri[j]]=true;
            if(i%pri[j]==0) {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            else {
                phi[i*pri[j]]=phi[i]*(pri[j]-1);
            }
        }
    }
    for(int i=1;i<N;i++) phi[i]+=phi[i-1];
}
ll Sphi(ll n){
    if(n<N) return phi[n];
    if(mp_phi[n]) return mp_phi[n];
    ll ans=n*(n+1)/2;
    for(ll l=2,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans-=Sphi(n/l)*(r-l+1);
    }
    return mp_phi[n]=ans;
}

例题