莫比乌斯反演

大家好，欢迎来到IT知识分享网。

莫比乌斯反演

莫比乌斯函数

定义

性质

1.莫比乌斯函数是一个数论函数，它是一个积性函数。

2.对任意正整数n有：

一些模板

线性筛莫比乌斯函数

update:浅说一下（感性理解）

其实很好想，根据\(\mu(d)\)的定义可以得到

当\(n\)为质数时，\(n\)显然只有一个质因数，即\(\mu(n)=-1\)

当\(n=p\cdot q\)且\(p\perp q\)，则\(n\)的质因数个数为\(p\)，\(q\)质因数个数和，那么\(\mu(n)=\mu(p)\cdot\mu(q)\)

一般线性筛的时候\(p\in prime\)，因此式子可以写成\(\mu(n)=-\mu(q)\)

当\(p|q\) 时，由于\(n\)含有平方因子，所以\(\mu(n)=0\)

总结一下，就是

然后就可以线性筛了（听说积性函数都可以线性筛出来）

int ss[N+5],mu[N+5],cnt,sum[N+5]; 
bool vs[N+5];
il void init(int n){
    for(ri unsigned int i=2;i<=n;++i){
        if(!vs[i]) ss[++cnt]=i,mu[i]=-1;
        for(ri unsigned int j=1;j<=cnt&&i*ss[j]<=n;++j){
            vs[i*ss[j]]=1;
            if(i%ss[j]==0) break;
            mu[i*ss[j]]=-mu[i];
        }
    }
    return;
}

算一个数的莫比乌斯函数

update:浅说一下（感性理解）

还是根据定义

由于\(\mu(n)\)与\(n\)的质因数的个数和出现次数有关，

可以暴力判断\(n\)的质因数及其次数（次数超过\(1\)则\(\mu(n)=0\)，直接\(break\)）

因为\(n\)大于\(\sqrt{n}\)的质因数最多只有一个，所以可以只循环到\(\sqrt{n}\)

il int mu(int n){
    int res=n,as=1;
    for(ri int i=2;i*i<=res;++i){//据说写i<=sqrt(res)快一些
        if(res%i==0){
            res/=i;
            if(res%i==0) return 0;
            as=-as;
        }
    }
    if(res>1) as=-as;
    return as;
}

数论分块

update:浅说一下（感性理解）

由于\(\lfloor\frac{n}{i}\rfloor\) 最多只有\(2\sqrt{n}\)种取值，所以可以将\(\lfloor\frac{n}{i}\rfloor\)值相同的数一起计算，复杂度\(O(\sqrt{n})\)

关于为什么最多\(1\sqrt{n}\)种取值：
对于\(i\le\sqrt{n}\)，\(\lfloor\frac{n}{i}\rfloor\) 有\(\sqrt{n}\)种取值（就\(\sqrt{n}\)个\(i\)）
对于\(i>\sqrt{n}\)，\(\lfloor\frac{n}{i}\rfloor\le\sqrt{n}\)（\(i\cdot\lfloor\frac{n}{i}\rfloor\)不能大于\(n\)）， 也只有\(\sqrt{n}\)种取值

关于右边界\(r=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor\)（使得\(\lfloor\frac{n}{l}\rfloor=\lfloor\frac{n}{r_0}\rfloor\)成立的最大\(r_0\)）：
令\(k=\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{l}\rfloor\)，则\(k\le\frac{n}{i}\)（都叫向下取整了）
所以\(\lfloor\frac{n}{k}\rfloor\ge\lfloor\frac{n}{\frac{n}{i}}\rfloor=\lfloor i\rfloor=i\)
则\(r=i_{max}=\lfloor\frac{n}{k}\rfloor=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor\)

il int sol(int n,int m){
    int as=0;
    for(ri int l=1,r=0;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        as+=(sum[r]-sum[l-1])*(n/l)*(m/l);
    }  
    retrun as;
}

一些式子

常用trick

关于gcd

将上式 \({n}\) 替换成\({gcd(i,j)}\)可推得

于是可以得到

把\(d\)提到前面，可得

这样就可用线性筛加数论分块\(O(n+Q\cdot\sqrt{n})\)求解啦~

关于反演

• \[\text{若有}f(n)=\sum_{d\mid n}g(d)\text{，则有}g(n)=\sum_{ d\mid n}μ(d)\cdot f({\frac{n}{d}}) \]

• \[\text{若有}f(n)=\sum_{{n\mid d}}g(d)\text{，则有}g(n)=\sum_{n\mid d} μ({\frac{d}{n}})\cdot f(d) \]

其他

狄利克雷卷积

• 定义

1. 对于两个数论函数\(f(x)\)和\(g(x)\),则它们的狄利克雷卷积得到的结果\(h(x)\)定义为：\(h(x)=\sum_{d\mid x}f(d)\cdot g(\frac{x}{d})=\sum_{a\cdot b}f(a)\cdot g(b)\),简记为\(h=f* g\)

2. 单位函数\(\epsilon:\epsilon(n)=\lbrack n=1\rbrack,\)

3. 幂函数\(id:id_{k}(n)=n^k\)

4. 常数函数\(I:I(n)=1,\)

5. 恒等函数\(id:id(n)=n=id_1(n)\)

6. 对于所有的数论函数\(f(n)\)，均有\(f(n) * I(n)=I(n) * f(n)=f(n)\)

7. 积性函数逆元：\(f * g=\epsilon\)，称\(f,g\)互为逆元，记\(f=g^{-1}\)，逆元是唯一的

• 性质

1. 交换律:设\(f，g\)为任意二个数论函数，则\(f * g=g * f\)

2. 结合律:设\(f，g，h\)为任意三个数论函数，则\((f * g) * h = f * (g * h)\)

3. 分配律:\((f+g)* h=f* h+g* h\)

4. 等式的性质:\(f=g\)的充要条件是\(f* h=g* h，\)其中数论函数\(h(x)\)要满足\(h(1)\ne 0\)

• 一些结论

1. 两个积性函数的 \(Dirichlet\) 卷积也是积性函数

2. 积性函数的逆元也是积性函数

关于莫反

1. \(\mu* I=\epsilon\)

2. \(I=\mu^{-1}\)

3. \(\varphi=\mu* id，\varphi* I=id\)

4. \(\varphi(n)= \sum_{d\mid n}d \cdot \mu(\frac{n}{d})\)

与其他函数的关系

• 1. 梅滕斯函数

莫比乌斯函数的求和函数，被称为梅滕斯函数，$$M(x)=\sum_{n\le x}\mu(n)$$

• 2. 生成函数

莫比乌斯函数有多个生成函数，其中一个与黎曼的\(\zeta(s)\)有关：$$\sum_{n=1}^{\infty}\frac{\mu(n)}{n ^ s}=\frac{1}{\delta(s)}$$

• 3. 无穷级函数

以下是关于莫比乌斯函数的一些无穷级数

资料

OvO~

练习题

莫反的一些练习题（1）
莫反的一些练习题（2）

edit