莫比乌斯反演_IT分享知识网

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

莫比乌斯反演

莫比乌斯函数

定义

\[\mu(d)=\begin{cases} 1 & \text{若}d=1\\ (-1)^r & \text{若}d\text{无平方数因数，且}d=p_1\cdot p_2……p_r\\ 0 & \text{若}d\text{有大于}1\text{的平方数因数} \end{cases}\]

性质

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

\[\sum_{d|n}\mu(d)=\begin{cases} 1 &(n=1)\\ 0 &(n\ne1) \end{cases}\]

2.对任意正整数n有：

\[\sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{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$

总结一下，就是

\[\mu(n)=\begin{cases} -1 & n=p (p\in prime) \\ -\mu(q) &n=p\cdot q,p\perp q\\ 0 &n=p\cdot q,p\vert q\\ \end{cases} \]

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

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

\[\sum_{d \mid n}μ(d)=[n=1] \]

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

\[\sum_{d \mid gcd(i,j)}μ(d)=[gcd(i,j)=1] \]

于是可以得到

\[\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d \mid gcd(i,j)}\mu(d) \]

把$d$提到前面，可得

\[\begin{align*} s &=\sum_{d=1}^{n}μ(d)\cdot\sum_{i}^{\lfloor\frac{n}{d}\rfloor}1\cdot\sum_{j}^{\lfloor\frac{m}{d}\rfloor}1 \\&=\sum_{d=1}^{n}μ(d)\cdot\lfloor\frac{n}{d}\rfloor\cdot\lfloor\frac{m}{d}\rfloor \end{align*}\]

这样就可用线性筛加数论分块$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) \]

其他

狄利克雷卷积

定义

对于两个数论函数$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$
单位函数$\epsilon:\epsilon(n)=\lbrack n=1\rbrack,$
幂函数$id:id_{k}(n)=n^k$
常数函数$I:I(n)=1,$
恒等函数$id:id(n)=n=id_1(n)$
对于所有的数论函数$f(n)$，均有$f(n) * I(n)=I(n) * f(n)=f(n)$
积性函数逆元：$f * g=\epsilon$，称$f,g$互为逆元，记$f=g^{-1}$，逆元是唯一的

性质

交换律:设$f，g$为任意二个数论函数，则$f * g=g * f$
结合律:设$f，g，h$为任意三个数论函数，则$(f * g) * h = f * (g * h)$
分配律:$(f+g)* h=f* h+g* h$
等式的性质:$f=g$的充要条件是$f* h=g* h，$其中数论函数$h(x)$要满足$h(1)\ne 0$

一些结论

两个积性函数的 $Dirichlet$ 卷积也是积性函数
积性函数的逆元也是积性函数

关于莫反

$\mu* I=\epsilon$
$I=\mu^{-1}$
$\varphi=\mu* id，\varphi* I=id$
$\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. 无穷级函数

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

\[\begin{align*} &1)\sum_{n=1}^{\infty}\frac{\mu(n)\cdot x^n}{1-x^n}=x \\&2)\sum_{n=1}^{\infty}\frac{\mu(n)}{n}=0 \\&3)\sum_{n=1}^{\infty}\frac{\mu(n)\cdot \ln n}{n}=-1 \end{align*}\]

资料

OvO~

练习题

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

edit

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/30974.html

莫比乌斯反演