数论函数、狄利克雷卷积、莫比乌斯反演和杜教筛

数论函数

常见的数论函数：

欧拉函数

$$varphi(n)=sum_{i=1}^{n}[(n, i)=1]$$

元函数

$$ epsilon(n)=[n=1]$$

恒等函数

$$1(n)=1$$

标号函数

$$Id(n)=n$$

除数函数

$$sigma(k, x)=sum_{d mid x} d^{k}$$

$k$省略时默认$k=1$

莫比乌斯函数

设$x$的唯一分解式为$x=p_{1}^{c_{1}} p_{2}^{c 2} ldots p_{k}^{c k}$，则

$$mu(x)=left{egin{array}{ll}
1 & x=1 \
(-1)^{m} & forall i in[1, k], c_{i}=1 \
0 & ext { otherwise }
end{array} ight.$$

狄利克雷卷积

定义

对于两个数论函数$f$和$g$，其狄利克雷卷积定义为

$$(f * g)(n)=sum_{d mid n} f(d) cdot gleft(frac{n}{d} ight)$$

函数积性

如果$f$和$g$都是积性函数，则$(f*g)$也是积性函数

常见数论函数的狄利克雷卷积

莫比乌斯函数

$$mu * 1=epsilon$$

欧拉函数

$$varphi * 1=i d$$

莫比乌斯反演

定义$F(n)$和$f(n)$是定义在非负整数几何上的两个函数

形式一

$$F(n)=sum_{n|d}f(d)$$

$$f(n)=sum_{n|d}mu(frac{d}{n})F(d)$$

形式二

$$F(n)=sum_{d|n}f(d)$$

$$f(n)=sum_{d|n}mu(d)F(lfloorfrac{n}{d} floor)$$

杜教筛

证明

已知数论函数$f(x)$，要求$sum_{i=1}^n f(i)$

构造两个积性函数$h$和$g$，使$f*g=h$

记$S(n)=sum_{i=1}^n f(i)$

egin{array}{c}
sum_{i=1}^{n} h(i)&=&sum_{i=1}^{n} sum_{d mid i} g(d) cdot fleft(frac{i}{d} ight)\
sum_{i=1}^{n} h(i)&=&sum_{d=1}^{n} g(d) cdot sum_{i=1}^{leftlfloorfrac{n}{d} ight floor} f(i) \
sum_{i=1}^{n} h(i)&=&sum_{d=1}^{n} g(d) cdot Sleft(leftlfloorfrac{n}{d} ight floor ight)
end{array}

egin{array}{l}
sum_{i=1}^{n} h(i)&=g(1) cdot S(n)+sum_{d=2}^{n} g(d) cdot Sleft(leftlfloorfrac{n}{d} ight floor ight) \
g(1) S(n)&=sum_{i=1}^{n} h(i)-sum_{d=2}^{n} g(d) cdot Sleft(leftlfloorfrac{n}{d} ight floor ight)
end{array}

代码

int djs2(int x)
{
    if(x<=9000000)//线性筛预处理 
        return mu[x];
    if(w2[x])//map记忆化搜索 
        return w2[x];
    int ret=1;
    for(int i=2;i<=x;)//整除分块 
    {
        int j=x/(x/i);
        ret-=(j-i+1)*djs2(x/i);
        i=j+1;
    }
    return w2[x]=ret;
}