Loading...

莫比乌斯反演 学习笔记

check评论:0 条 remove_red_eye浏览量:43 change_historyTags:编程学习笔记
作者 : Decoration date_range日期 : 2018-11-07

终于把莫比乌斯反演这个好久没动的坑啃了qaq

先来说一下莫比乌斯函数

我们定义$\mu(1)= 1$,当$i=\Pi_{k=1}^K p_k(p_k\in prime)$的时候,$\mu(i)=(-1)^k$,其他情况下$\mu(i)=0$

然后我们来说下这个函数的性质

首先,这是个积性函数,就是说当$gcd(i,j)=1$时,$\mu(i\times j)=\mu(i)\times \mu(j)$

并且可以得到$\sum_{d|n} \mu(d)=1(n=1)$,这个公式在后面会有很大的用处

接下来说莫比乌斯反演

我们定义$F(n)=\sum_{d|n}f(d)$

那么显而易见$f(n)=\sum_{d| n}\mu(\frac{n}{d})F(d)$

当然,也可以得到$f(n)=\sum_{d| n}\mu(d)F(\frac{n}{d})$

博主不会证明,所以证明就鸽了

例题:洛谷$P2568\ GCD$

这道题本来是用欧拉函数的,可是我想练一下莫比乌斯反演qwq

那么来开心的推式子吧:

题目要求的$ans=\sum_{k=1}^K \sum_{i=1}^n \sum_{j=1}^n (gcd(i,j)=p_i)$,其中$p_i$是质数

$i,j$上界同除以$p_i$,得到$ans=\sum_{k=1}^K\sum_{i=1}^{\lfloor\frac{n}{p_i}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p_i}\rfloor}(gcd(i,j)=1)$

然后我们看到右边那个$gcd(i,j)=1$,想一想,什么东西的和等于$1$啊qwq?

当然是之前提到的公式$\sum_{d|n}\mu(d)=1(n=1)$啦!

我们把公式里的$n$换成$gcd(i,j)$,带入原式,即$ans=\sum_{k=1}^K\sum_{i=1}^{\lfloor\frac{n}{p_i}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p_i}\rfloor}\sum_{d|gcd(i,j)}\mu(d)$

我们再来想一想,$d|gcd(i,j)$是不是说明$d|i$并且$d|j$?

则$ans=\sum_{k=1}^K\sum_{d}\mu(d)\sum_{d|i}^{\lfloor\frac{n}{p_i}\rfloor}\sum_{d|j}^{\lfloor\frac{n}{p_i}\rfloor}$

然后发现我们枚举$d$的话,右边两个$\sum$是不是正好就等于$\lfloor\frac{\frac{n}{p}}{d}\rfloor ^2$?

然后把$p$移下来,得到$\lfloor\frac{n}{dp}\rfloor^2$

所以$ans=\sum_{k=1}^K\lfloor\frac{n}{dp}\rfloor^2\sum_d\mu(d)$

$dp$看着就烦,我们把它换掉

设$T=dp$,则

$ans=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2\sum_{t|T}\mu(t)$

左边的我们可以发现用数论分块是比较好的

而右边的,我们统计个前缀和就好了

上代码qwq

#include <bits/stdc++.h>
using namespace std;
int prime[4000020],cnt,mu[10000010],n,vis[10000010];
long long sum[10000010];
void pre()
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt,i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j*prime[i]<=n;j++)
        {
            sum[j*prime[i]]+=mu[j];
        }
    }
    for(int i=2;i<=n;i++)
    {
        sum[i]+=sum[i-1];
    }
}
int main()
{
    cin>>n;
    pre();
    long long ans=0;
    for(int t=1;t<=n;t++)
    {
        int l=t,r=(n/(n/l));
        t=r;
        ans+=(sum[r]-sum[l-1])*(n/l)*(n/l);
    }
    cout<<ans;
}

数论板子小结 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名