莫比乌斯反演

· · 个人记录

定理

设 F(x) 与 f(x) 是定义在 N^* 上的两个函数

满足

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

则有

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

其中 μ(d) 为莫比乌斯函数

证明

F(n)=\sum_{d|n}f(d) \Downarrow f(n)=\sum_{d|n}F(\frac{n}{d})\mu(d) ∵F(\frac{n}{d})=\sum_{x|\frac{n}{d}}f(x) ∴F(\frac{n}{d})=\sum_{d|n}\mu(d)F(\frac{n}{d}) \Downarrow f(n)=\sum_{d|n}\mu(d)\sum_{x|\frac{n}{d}}f(x) \qquad\;\;=\sum_{x|n}(\sum_{d|\frac{n}{x}}f(x)\mu(d)) \qquad\;\;=\sum_{x|n}(f(x)\sum_{d|\frac{n}{x}}\mu(d)) \qquad\qquad =\begin{cases} f(n)* 1\qquad ,x=n \\ \sum_{x|n}f(x)* 0,x<n \end{cases} ∴f(n)=\sum_{x|n}f(x)\sum_{d|\frac{n}{x}}\mu(d)=f(n)

补充说明

1.若对于一个数对 (d,x) ，满足 d|n 和 x|\frac{n}{d} ，则一定有 x|n 和 d|\frac{n}{x}

2.对一个确定的 d

\sum_{d|n}(\sum_{x|\frac{n}{d}}\mu(d)f(x))\Longleftrightarrow \sum_{x|n}(\sum_{d|\frac{n}{x}}f(x)\mu(d))

常用的反演变形

F(k)=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}f(ik) f(k)=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}F(ik)\mu(i)

整除分块

这次不要脸还是在此博客（这次全是抄的）

“对于每一个 \lfloor\frac{n}{i}\rfloor 我们可以通过打表(或理性的证明)可以发现：有许多 \lfloor\frac{n}{i}\rfloor 的值是一样的，而且它们呈一个块状分布；再通过打表之类的各种方法,我们惊喜的发现对于每一个值相同的块，它的最后一个数就是 n/(n/i) 。得出这个结论后，我们就可以做的 O(\sqrt n)处理了。"

代码:

for(int l=1,r;l<=n;l=r+1)
{
      r=n/(n/l);
      ans+=(r-l+1)*(n/l);
}

进阶: 对于

\sum_{i=1}^n\lfloor\frac{k}{i}\rfloor

代码为

for(ll l=1,r;l<=n;l=r+1)
{
    if(k/l) r=min(k/(k/l),n);
    else r=n;
    ans-=((r+l)*(r-l+1)/2)*(k/l);
}

例题 P2257 YY的GCD

（依旧不要脸地改编自这个题解）

给定 N, M ,求 1<=x<=N , 1<=y<=M 且 gcd(x, y) 为质数的 (x, y) 有多少对，即

\sum_{i=1}^n\sum_{j=1}^m[gcd(x,y)=prime]

与 gcd 有关的莫比乌斯反演，一般可设 f(d) 为 gcd(i,j)=d 的个数 ，F(n) 为 gcd(i,j)=d 和 d 的倍数的个数

f(d)=\sum_{i=1}^n\sum_{j=1}^m[gcd(x,y)=d] F(n)=\sum_{n|d}f(d)=\lfloor\frac{N}{n}\rfloor\lfloor\frac{M}{n}\rfloor ∴f(n)=\sum_{n|d}\mu(\lfloor\frac{d}{n}\rfloor)F(d) ∵Ans=\sum_{p\in prime}\sum_{i=1}^n\sum_{j=1}^m[gcd(x,y)=p]

代入 f(p)

∴Ans=\sum_{p\in prime}f(p) $$Ans=\sum_{p\in prime}\sum_{p|d}\mu(\lfloor\frac{d}{p}\rfloor)F(d)$$ ($\sum_{p|d}$ 为枚举 $p$ 的倍数) 替换枚举项为 $\lfloor\frac{d}{p}\rfloor$ ， $$Ans=\sum_{p\in prime}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)F(dp)$$ （对此行做一些解释： $$∵p|d_1∴\frac{d_1}{p}\in Z$$ $$d_2=\frac{d_1}{p},p=\lfloor\frac{d_1}{d_2}\rfloor$$ $$∴\sum_{p|d_1}\mu(\lfloor\frac{d_1}{p}\rfloor)F(d_1)=\sum_{d_2=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d_2)F(d_2p)$$ 若 $d_2>min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)$ ，那么会超出 $N,M$的限制） $$Ans=\sum_{p\in prime}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor$$ 将 $dp$ 替换为 $T Ans=\sum_{T=1}^{min(n,m)}\sum_{t|T,t\in prime}\mu(\frac{T}{t})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor ∴Ans=\sum_{T=1}^{min(n,m)}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor(\sum_{t|T}\mu(\frac{T}{t}))

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN=10000000;
int t,m,n,cnt;
int miu[MAXN+1],prime[MAXN+1];//miu记录μ值，prime记录质数 
ll ans;
ll sum[MAXN+1],g[MAXN+1];//sum记录前缀和，g[n]记录n的质因子的μ的和 
bool vis[MAXN+1];//记录是否为质数（表现为是否遍历过） 

void read(int &x)
{
    x=0;
    char c=getchar(),last=' ';
    while(c<'0'||c>'9'){
        last=c;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c-'0');
        c=getchar();
    }
}

void print(ll x)
{
    int cnt=0,a[18];
    do
    {
        a[++cnt]=x%10;
        x/=10;
    }while(x);
    for(int i=cnt;i>=1;i--)putchar(a[i]+'0');
    puts("");
}

void make_miu(int n)
{
    miu[1]=1;
    for(int i=2;i<=n;++i) 
    {
        if(!vis[i])
        {
            miu[i]=-1;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=n;++j) 
        {
            vis[prime[j]*i]=true;
            if(i%prime[j]==0) break;
            else miu[prime[j]*i]=-miu[i];
        }
    }
}

void prefix(int n)//求出从1到n的前缀和 
{
    for(int i=1;i<=cnt;++i)
        for(int j=1;j*prime[i]<=n;++j) g[j*prime[i]]+=miu[j];
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+(ll)g[i];
}

int main()
{
    read(t);
    make_miu(MAXN);
    prefix(MAXN);
    for(int i=1;i<=t;++i)
    {
        read(n); read(m);
        ans=0;
        if(n>m) swap(n,m);
        for(int l=1,r;l<=n;l=r+1)//分块 
        {
            r=min(n/(n/l),m/(m/l));//取小值，使生成的数不会超过每一小块的范围 
            ans+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);//套sigma公式,1ll转换为long long 
        }
        print(ans);
    }
    return 0;
}