莫比乌斯反演学习笔记

前置知识

简单数论知识

\(d\mid n\) 表示 \(n\%d==0\)

\([f]\) 艾弗森括号，在 \(f\) 为真时为 \(1\) 否则为 \(0\)

数论分块

很多莫比乌斯反演的题目都需要用到数论分块，所以先讲讲基础的数论分块。

数论分块可以快速求出其中一部分内容关于 \(\left\lfloor \frac{n}{i} \right\rfloor\) 的式子。

注意到 \(\left\lfloor \frac{n}{i} \right\rfloor\) 的结果数量是 \(\sqrt n\) 级别的。

那么我们考虑对于每一个 \(\left\lfloor \frac{n}{i} \right\rfloor\) 进行计算。

首先我们需要锁定每一个 \(\left\lfloor \frac{n}{i} \right\rfloor\) 对应的值的范围。

我们已经知道这次要处理的值其左边为 \(l\) 的话，假设 \(k=\left\lfloor \frac{n}{l} \right\rfloor\) 为了让 \(r\) 作为最大的满足 \(k=\left\lfloor \frac{n}{r} \right\rfloor\) ，显然 \(kr\le n\)。那么 \(r\) 最大就是 \(\left\lfloor \frac{n}{k} \right\rfloor\) 了。

所以每次区间的 \(r\) 就是 \(\left\lfloor \frac{n}{\left\lfloor \frac{n}{l} \right\rfloor} \right\rfloor\) 了。

莫比乌斯函数

莫比乌斯函数用 \(\mu(n)\) 表示。

\(\mu(n) = \begin{cases} 1, & n = 1 \\[4pt] 0, & n \text{ 含有平方因子} \\[4pt] (-1)^k, & n \text{ 是 } k \text{ 个互异质数的乘积} \end{cases}\)

这个玩意究竟有什么用？其实这相当于一个容斥系数，可以帮助我们求一些倍数关系的式子。

核心性质：\(\sum_{d\mid n}\mu(d)=[n=1]\)

由于所有带有平方因子的全部都为 \(0\) 所以在求和时只需要考虑每个质因子是否有出现即可，也就是出现次数最多为 \(1\)。

那么枚举每所有质因子数量，假设有 \(k\) 个质因子，即为 \( \sum_{j=0}^{k} \binom{k}{j} (-1)^j = (1-1)^k = 0^k \)

只有在 \(n=1\) 时，可以得到答案为 \(1\)。

因此得证。

莫比乌斯反演

形式一

\( F(n) = \sum_{d \mid n} f(d) \quad \Longleftrightarrow \quad f(n) = \sum_{d \mid n} \mu\!\left(\frac{n}{d}\right) F(d) \)

先将 \(F(n)\) 代入，然后调整求和顺序，将 \(\mu(n)\) 求和单独放到最后。

得到 \(\sum_{k\mid n}f(k)\sum_{d\mid \frac n k}\mu(d)\)

可以通过关键性质进行转换得到 \(\sum_{k\mid n}f(k)[\frac n k =1]\)

显然结果就是 \(f(n)\) 了。

由此，得证。

形式二

\(F(n) = \sum_{\substack{n \mid d \\ d \le N}} f(d) \quad \Longleftrightarrow \quad f(n) = \sum_{\substack{n \mid d \\ d \le N}} \mu\!\left(\frac{d}{n}\right) F(d)\)

结论可以通过如同之前的方式证明得到。

应用

莫比乌斯反演最为核心的点在于将看起来不太好处理的判断类问题转化为求和形式，通常在一些对 gcd 进行计算的地方可以用到。

Problem b

题

比较板子了。

首先这个问题是可以差分的，直接把其拆成四个询问即可，假设本次处理 \(1\le x\le n,1\le y \le m\)。

\[\begin{aligned} \sum_{x=1}^n \sum_{y=1}^m [\gcd(x,y)=k] &= \sum_{x'=1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum_{y'=1}^{\left\lfloor \frac{m}{k} \right\rfloor} [\gcd(x',y')=1] \quad \left( \text{令 } x=kx',\; y=ky' \right) \\[6pt] &= \sum_{x'=1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum_{y'=1}^{\left\lfloor \frac{m}{k} \right\rfloor} \sum_{d \mid \gcd(x',y')} \mu(d) \quad \left( [\gcd=1] = \sum_{d \mid \gcd} \mu(d) \right) \\[6pt] &= \sum_{d=1}^{\min\left(\left\lfloor \frac{n}{k} \right\rfloor,\; \left\lfloor \frac{m}{k} \right\rfloor\right)} \mu(d) \sum_{x''=1}^{\left\lfloor \frac{n}{kd} \right\rfloor} \sum_{y''=1}^{\left\lfloor \frac{m}{kd} \right\rfloor} 1 \quad \left( \text{交换求和顺序，} x'=dx'',\; y'=dy'' \right) \\[6pt] &= \sum_{d=1}^{\min\left(\left\lfloor \frac{n}{k} \right\rfloor,\; \left\lfloor \frac{m}{k} \right\rfloor\right)} \mu(d) \left\lfloor \frac{n}{kd} \right\rfloor \left\lfloor \frac{m}{kd} \right\rfloor \end{aligned} \]

可以使用数论分块进行处理。

看看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,pri[50005],mu[50005],pre[50005],cnt;
bool f[50005];
void init(){mu[1]=1,pre[1]=1;for(int i=2;i<=50000;i++){if(!f[i]){pri[++cnt]=i;mu[i]=-1;}for(int j=1;j<=cnt&&pri[j]*i<=50000;j++){f[pri[j]*i]=1;if(i%pri[j]==0)break;mu[pri[j]*i]=-mu[i];}pre[i]=pre[i-1]+mu[i];}
}
int solve(int n,int m,int k){int ans=0;n/=k,m/=k;for(int l=1,r;l<=min(n,m);l=r+1){r=min(n/(n/l),m/(m/l));ans+=(pre[r]-pre[l-1])*(n/l)*(m/l);}return ans;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);init();cin>>n;for(int i=1,a,b,c,d,k;i<=n;i++){cin>>a>>b>>c>>d>>k;cout<<solve(b,d,k)-solve(a-1,d,k)-solve(b,c-1,k)+solve(a-1,c-1,k)<<endl;}return 0;
}

Crash的数字表格

题

依然推式子。

\[\newcommand{\lf}{\left\lfloor} \newcommand{\rf}{\right\rfloor}\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m} \operatorname{lcm}(i,j) &= \sum_{i=1}^{n}\sum_{j=1}^{m} \frac{i j}{\gcd(i,j)} \\ &= \sum_{d=1}^{\min(n,m)} \sum_{i=1}^{\lf \frac{n}{d} \rf} \sum_{j=1}^{\lf \frac{m}{d} \rf} i j d \,[\gcd(i,j)=1] \\ &= \sum_{d=1}^{\min(n,m)} d \sum_{i=1}^{\lf \frac{n}{d} \rf} \sum_{j=1}^{\lf \frac{m}{d} \rf} i j \,[\gcd(i,j)=1] \\ &= \sum_{d=1}^{\min(n,m)} d \sum_{i=1}^{\lf \frac{n}{d} \rf} \sum_{j=1}^{\lf \frac{m}{d} \rf} i j \sum_{t\mid \gcd(i,j)} \mu(t) \\ &= \sum_{d=1}^{\min(n,m)} d \sum_{t=1}^{\min(\lf \frac{n}{d} \rf, \lf \frac{m}{d} \rf)} \mu(t) \sum_{i=1}^{\lf \frac{n}{dt} \rf} \sum_{j=1}^{\lf \frac{m}{dt} \rf} (i t)(j t) \\ &= \sum_{d=1}^{\min(n,m)} d \sum_{t=1}^{\min(\lf \frac{n}{d} \rf, \lf \frac{m}{d} \rf)} t^{2} \mu(t) \left( \sum_{i=1}^{\lf \frac{n}{dt} \rf} i \right) \left( \sum_{j=1}^{\lf \frac{m}{dt} \rf} j \right) \end{aligned} \]

显然对于式子的最后两个求和可以直接通过等差数列求和公式得到，前面两个求和各自使用一个数论分块即可解决。

看看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=20101009,inv2=(mod+1)/2;
int n,m,mu[10000005],cnt,pri[10000005],pre[10000005];
bool f[10000005];
void init(int n){mu[1]=1;for(int i=2;i<=n;i++){if(!f[i]){pri[++cnt]=i;mu[i]=-1;}for(int j=1;j<=cnt&&pri[j]*i<=n;j++){f[i*pri[j]]=1;if(i%pri[j]==0)break;mu[i*pri[j]]=-mu[i];}}for(int i=1;i<=n;i++)pre[i]=(pre[i-1]+mu[i]*i%mod*i%mod)%mod;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;init(min(n,m));int ans=0;for(int d=1;d<=min(n,m);d++){int x=n/d,y=m/d;int res=0;for(int l=1,r;l<=min(x,y);l=r+1){r=min(x/(x/l),y/(y/l));res=res+(pre[r]-pre[l-1]+mod)%mod*((1+x/l)*(x/l)%mod*inv2%mod)%mod*((1+y/l)*(y/l)%mod*inv2%mod)%mod;}ans=(ans+d*res)%mod;}cout<<ans;return 0;
}