莫比乌斯反演¶
莫比乌斯函数¶
\(\mu(x)=\begin{cases}0 &\exist d_i\geq 1 \\(-1)^k & \forall d_i=1\end{cases}\)，\(d_i\)是x的质因子的次幂，k是x的质因子的个数。
性质：记\(s(n)=\sum\limits_{i|n}\mu(i)\)
有\(s(x)=\begin{cases}0 &n>1\\1 &n=1\end{cases}\)
证明：考虑n的约数i。根据定义，将质因数分解后得到质数为\(d_i\)，我们只需要考虑\(d_i\)要么是1要么是0的情况。并且如果d中有奇数个1，则\(\mu(i)\)为-1，否则为1。可以证明s(n)=0。n=1时为特例。
莫比乌斯反演定理¶
定义在正整数域的函数
\(F(n)=\sum\limits_{i|n}f(i)\)，则\(f(n)=\sum\limits_{i|n}\mu(i)F(\frac{n}{i})\)。这样说如果对于一道求f(n)的题目，其f(n)难求，但是F(n)好求，则可以使用该方程。
证明如下图：（下文中\(g(x)\)即\(F(x)\)）
莫比乌斯反演的推导¶
狄利克雷卷积¶
我们新定义一个符号(定义新运算) \(*\)
\(h,f,g\) 都是函数名称
定义 \(h=f*g\) : \(h=f*g=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}d)g(d)\\h=f*g=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}d)g(d)\)
再定义几个函数
- \(\sum\) 函数 (这里只是一个函数名字而已) 有
对于任意x 有\(\sum\) (x)=1
- \(1(x)\) 对于任意x
有\(1(x)\) =\(x\)
- 单位元 \(e\)
有 e(n)=[n=1] (这个式子的意思是当n=1时 值为1 否则为0)
这个单位元有一个性质 :\(f*e=e\)
乘法有逆元 狄利克雷卷积也有逆元
逆元: 如果对于f存在 \(f*g=e\) 那么就称\(g\)为\(f\)的逆元
莫比乌斯反演¶
首先介绍一个东西 叫做莫比乌斯函数 \(\mu\)
定义\(\sum\) 函数的逆元为 \(\mu\)
\(\mu * \sum= e\) 写成普通的形式 \(\sum_{d|n}\mu(d)=[n=1]\)
带入之后发现\(\mu\) 的取值 \(\mu(n) = \begin{cases}1,n=1\\0,存在一个平方数是n的因子\\(-1)^m,m是n的质因子个数\end{cases}\)
从上面我们得到了一个重要的结论1:
\(\sum_{d|n}\mu(d)=[n=1]\)
莫比乌斯反演常用推导¶
推导1：\(A=\sum_{i≤n} \sum_{d|i} \mu(d)\)¶
先枚举 i, 再考虑 i所有的约数 等价于是 先枚举d 再考虑d在范围内所有的倍数
所以 \(\sum_{i≤n} \sum_{d|i} \mu(d)=\sum_{d≤n} \lfloor \frac{n}{d} \rfloor \mu(d)\)
这个作为结论2
推导2： \(B=\sum_{i≤n} \sum_{j≤m} [(i,j)=1]\)¶
用结论1
\(B=\sum_{i≤n} \sum_{j≤m} \sum_{d|(i,j)} \mu(d)\)
\(=\sum_{i≤n} \sum_{j≤m} \sum_{d|i} \sum_{d|j} \mu(d)\)
\(=\sum_{i≤n} \sum_{d|i} \sum_{j≤m} \sum_{d|j} \mu(d)\)
用结论2
\(B=\sum_{i≤n} \sum_{d|i}\sum_{d≤m} \lfloor \frac{m}{d} \rfloor \mu(d)\)
\(=\sum_{d≤n}\lfloor \frac{n}{d} \rfloor\sum_{d≤m} \lfloor \frac{m}{d} \rfloor \mu(d)\)
\(=\sum_{d≤min(n,m)} \mu(d)\lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor\)
这个作为结论3
莫比乌斯反演入门题讲解请转到例题 #3
例题 #1 [HAOI2011] Problem b¶
弱化版请转到：[POI2007] ZAP-Queries
题目描述
对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a \le x \le b\)，\(c \le y \le d\)，且 \(\gcd(x,y) = k\)，\(\gcd(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。
思路
首先是差分转化，将矩形转化为前缀和
\(F(k)=\sum\limits_{x=1}^a\sum\limits_{y=1}^b [k|\gcd(x,y)]\)
\(f(k)=\sum\limits_{x=1}^a\sum\limits_{y=1}^b [k=\gcd(x,y)]\)，即题目要求的内容。
那么\(F(n)=\sum\limits_{n|i}f(i)\)
\(f(n)=\sum\limits_{n|i}\mu(\frac{i}{n})F(i)\)
可以知道\(k|\gcd(x,y)=k|x,k|y\)，故\(F(k)=\sum\limits_{x=1}^a\sum\limits_{y=1}^b [k|\gcd(x,y)]=\lfloor \frac{a}{k}\rfloor\times \lfloor \frac{b}{k}\rfloor\)
\(f(n)=\sum\limits_{n|i}\mu(\frac{i}{n})\lfloor \frac{a}{i}\rfloor\times \lfloor \frac{b}{i}\rfloor\)，令\(D=\frac{i}{n}\)，则\(f(n)=\sum\limits_{D}\mu(D)\lfloor \frac{a}{Dn}\rfloor\times \lfloor \frac{b}{Dn}\rfloor\)，a,b,n都是定值，只有D是变量。
这里插播一个\(g(x)=k/(k/x)\)，表示以\(\lfloor \frac{k}{x}\rfloor\)整数分块，\(x\)所在的块的最后一个数字。/表示c++除法
/*
Code by Ntsc
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define ps second
#define pf first
#define rd read()
inline int read()
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int N = 6e5+5;
int mu[N],st[N];
int n,cnt;
int sum[N];
int prime[N];
void init(){
mu[1]=1;
for(int i=2;i<N;i++){
if(!st[i])prime[++cnt]=i,mu[i]=-1;
for(int j=1;prime[j]*i<N;j++){
st[prime[j]*i]=1;
if(!(i%prime[j]))break;
mu[prime[j]*i]=-mu[i];//根据定义偶正奇负
}
}
for(int i=1;i<N;i++)sum[i]=sum[i-1]+mu[i];
}
int g(int k,int x){
return k/(k/x);
}
int f(int a,int b,int k){
a/=k,b/=k;
n=min(a,b);
int mn=min(a,b),res=0;
for(int l=1,r;l<=n;l=r+1){
r=min(n,min(g(a,l),g(b,l)));
res+=(sum[r]-sum[l-1])*(a/l)*(b/l);
}
return res;
}
signed main(){
init();
int T=rd;
while(T--){
int a=rd,b=rd,c=rd,d=rd,k=rd;
cout<<f(b,d,k)-f(a-1,d,k)-f(b,c-1,k)+f(a-1,c-1,k)<<endl;
}
}
对于 \(100\%\) 的数据满足：\(1 \le n,k \le 5 \times 10^4\)，\(1 \le a \le b \le 5 \times 10^4\)，\(1 \le c \le d \le 5 \times 10^4\)。
例题 #2 [SDOI2015] 约数个数和¶
题目描述
设 \(d(x)\) 为 \(x\) 的约数个数，给定 \(n,m\)，求 \(\sum_{i=1}^n\sum_{j=1}^md(ij)\)
思路¶
\(d(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\)，这个结论很重要
证明：
设i质因数分解后的指数为\(a_i\)，j质因数分解后的指数为\(b_i\)，那么首先可以知道ij的质因数个数为\((a_1+b_1+1)(a_2+b_2+1)\dots(a_k+b_k+1)\)
我们再取ij的一个因数s=xy来说。对于\(p_1\)，为了满足x,y互质，则当x取\(p_1^i\)时，y只能取1。相同地，当y取\(p_1^i\)时，x只能取1。还有一种情况是两者都取1。那么合起来就有\(a_1+b_1+1\)种取值。这恰恰和计算质因数个数的式子一样了。
则\(\sum_{i=1}^n\sum_{j=1}^md(ij)=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\)。
设
\(f(q)=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[q=\gcd(x,y)]\)
\(F(q)=\sum\limits_{q|d}f(d)\)，则有\(f(q)=\sum\limits_{q|d}\mu(\frac{d}{q})F(d)\)
推导：
\(F(q)=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[q|\gcd(x,y)]\\=\sum_{x=1}^n\sum_{y=1}^m\sum_{i=kx,k\in\Z}^n\sum_{j=ky,k\in\Z}^m[q|\gcd(x,y)]\\=\sum_{x=1}^n\sum_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor[q|\gcd(x,y)]\)
设 \(x'=\frac{x}{q},y'=\frac{y}{q},n'=\frac{n}{q},m'=\frac{m}{q}\)
则上式等于
\(\sum_{x'=1}^{n'}\sum_{y'=1}^{m'}\lfloor\frac{n'}{x'}\rfloor\lfloor\frac{m'}{y'}\rfloor\\=(\sum_{x'=1}^{n'}\lfloor\frac{n'}{x'}\rfloor)(\sum_{y'=1}^{m'}\lfloor\frac{m'}{y'}\rfloor)\)
定义 \(h(n')=(\sum_{x'=1}^{n'}\lfloor\frac{n'}{x'}\rfloor)\)
则 \(F(q)=h(n')h(m')\)
\(f(q)=\sum\limits_{d=1}^n \mu(d)h(\frac{n}{d})h(\frac{m}{d})\)，整数分块优化即可。
/*
Code by Ntsc
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define ps second
#define pf first
#define rd read()
inline int read()
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int N = 5e4+5;
int mu[N],st[N];
int e,cnt;
int sum[N];
int h[N];
int prime[N];
int g(int k,int x){
return k/(k/x);
}
void init(){
mu[1]=1;
for(int i=2;i<N;i++){
if(!st[i])prime[++cnt]=i,mu[i]=-1;
for(int j=1;prime[j]*i<N;j++){
st[prime[j]*i]=1;
if(!(i%prime[j]))break;
mu[prime[j]*i]=-mu[i];//根据定义偶正奇负
}
}
for(int i=1;i<N;i++)sum[i]=sum[i-1]+mu[i];
for(int i=1;i<N;i++){
for(int l=1,r;l<=i;l=r+1){
r=min(i,g(i,l));
h[i]+=(r-l+1)*(i/l);
}
}
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
init();
int T=rd;
while(T--){
int n=rd,m=rd;
int res=0;
int k=min(n,m);
for(int l=1,r;l<=k;l=r+1){
r=min(min(g(n,l),g(m,l)),k);
res+=(sum[r]-sum[l-1])*h[n/l]*h[m/l];
}
cout<<res<<'\n';
}
}
【数据范围】 对于 \(100\%\) 的数据，\(1\le T,n,m \le 50000\)。
例题 #3 公约数的和¶
题目背景
有一天，TIBBAR 和 LXL 比赛谁先算出 \(1 \sim n\) 这 \(n\) 个数中每任意两个不同的数的最大公约数的和。LXL 还在敲一个复杂而冗长的程序，争取能在 \(100s\) 内出解。而 TIBBAR 则直接想 \(1s\) 秒过而获得完胜，请你帮他完成这个任务。
题目描述
给定 \(n\)，求 \(\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)\)
其中 \(\gcd(i, j)\) 表示 \(i\) 和 \(j\) 的最大公约数。
- 对于 \(100\%\) 的数据，保证 \(2 \leq n \leq 2 \times 10^6\)。
给定 \(n\)，求 \(\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)\)
首先让两个循环归一化
\(\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)=\frac{1}{2} \sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j)\)
我们来变形，要使用莫比乌斯反演，我们得要有一个\sum[x=1]的形式
\(Q:\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j)\\=\sum_{d≤n}d\times \sum_{i = 1}^n \sum_{j = 1 }^n [\gcd(i, j)=d]\\=\sum_{d≤n}d\times \sum_{i = 1}^{n/d} \sum_{j = 1}^{n/d} [\gcd(i, j)=1]\)
考虑莫比乌斯反演
\(f(n)=\sum\limits_{i|n}\mu(i)F(\frac{n}{i})\)
令\(A(n)=\sum_{i = 1}^{n} \sum_{j = 1}^{n} [\gcd(i, j)=1]\)
使用结论1：\(\sum_{d|n}\mu(d)=[n=1]\)
\(A =\sum_{i≤n} \sum_{j≤n} \sum_{d|\gcd(i,j)} \mu(d)\)
又有\(d|\gcd(i,j)\Leftrightarrow d|i且d|j\)
\(A=\sum_{i≤n} \sum_{d|i} \sum_{j≤n} \sum_{d|j} \mu(d)\)
考虑结论2：\(\sum_{i<=n} \sum_{d|i} \mu(d)=\sum_{d<=n} \lfloor \frac{n}{d} \rfloor \mu(d)\)
\(A=\sum_{d<=n} \lfloor \frac{n}{d} \rfloor \sum_{d<=n} \lfloor \frac{n}{d} \rfloor \mu(d)\)
这个可以使用数论分块和前缀和（维护区间的\(\mu()\)使用）在\(O(\sqrt n)\)解决。
则
\(Q:\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j)\\=\sum_{d≤n}d\times A(n/d)\)
我们发现A(n/d)也是可以使用数论分块做的，所以整体时间复杂度可以做到O(n)
其实，本题还有一个很简单的做法：
这里介绍一种nlogn的做法
设\(f[d]=∑∑[\gcd(i,j)=d]\)
\(F[d]=∑∑[d|\gcd(i,j)]\)，其中[d|\gcd(i,j)]表示d整除\gcd(i,j)返回1，否则返回0
不难看出F[d]=n/d*(n/d)
那么\(f[d]=F[d]-∑_{k>1}f[kd]\)
所以o(nlogn)扫一下就好了（主要是代码特别短）
然后\(ans=(d\times∑f[d]-n*(n+1)/2)/2\) 减去gcd(d,d)=d的和gcd(i,j)=gcd(j,i)重复的
const int N = 2e6 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
itn f[N];
void solve(){
itn ans=0;
itn n=rd;
for(int i=n;i;i--){
f[i]=n/i*(n/i);
for(itn j=i<<1;j<=n;j+=i)f[i]-=f[j];
ans+=f[i]*i;
}
ans-=n*(n+1)/2;
cout<<ans<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
\(\textbf{\huge AA}\) \(\textbf{\LARGE BB}\) \(\text{\large CC}\) \(\text{\small DD}\) $\textbf {\huge $ \mathbb{EE} \(}\) \(FF\) \(\large \frak {GG}\)