浅谈莫比乌斯反演
B1ueC4t
·
2018-12-11 19:11:02
·
个人记录
这可能是我写过最正经的一篇博客吧
先来看一个例子
设 ans = \sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j) ，求 ans
1 \leq n , m \leq 10^3
你可能会说，这不是简单吗，暴力枚举 i,j , 然后统计答案就好了啊
当如果我改一下题目呢？
设 ans = \sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j) ，T 组询问，对于每组询问，求 ans
1 \leq n , m \leq 10^5 , 1 \leq T \leq 10^5
这就不是暴力能解决了的
所以我们来引进一个新算法，那就是——莫比乌斯反演
数论函数
积性函数
如果一个函数的定义域为正整数，值域为复数，则称此函数为数论函数
对于数论函数f ，若对于任意互质的a,b \in \mathbf{Z^{+}} ，都有f(a\times b) = f(a) \times f(b) ，则称f 为积性函数
特别地，若对于任意不互质的a,b 也成立，则称f 为完全积性函数
这里列举几个常用的积性函数，对做题很有帮助：
元函数：e(n) = [n == 1]
恒等函数：I(n) = 1
单位函数：\varepsilon(n) = n
欧拉函数：\varphi(n) = \sum_{i=1}^{n}[gcd(i,n)==1]
莫比乌斯函数：\mu
这里通俗解释一下这些函数分别是什么意思
元函数：只有第一项为1 ，其他项都为0
恒等函数：所有项都为1
单位函数：第i 项函数值为i
欧拉函数：1 - n 中与n 互质的数的个数
莫比乌斯函数，emmm 这个上面解释的很清楚了
狄利克雷卷积
定义：
对于两个数论函数f(x) 和g(x) ，定义它们的狄利克雷卷积为(f\times g)(n) = \sum_{d|n}f(d)g(\frac{n}{d})
例如：(f\times g)(6) = f(1)g(6) + f(2)g(3) + f(3)g(2) +f(6)g(1)
性质：
结合律：( f \times g ) \times h = f\times (g\times h)
交换律：f \times g = g \times f
封闭性：数论函数的狄利克雷卷积一定是数论函数
这里列举几个常用的狄利克雷卷积：
\varepsilon = \varphi \times I \space \Leftrightarrow \space n = \sum_{d|n}\varphi(d)
e = \mu \times I \space \Leftrightarrow \space [n==1] = \sum_{d|n}\mu(d)
\varphi= \mu \times \varepsilon \space \Leftrightarrow \space \sum_{d|n}\mu(d)\times \frac{n}{d}
前两个就不做证明了，带入具体值都是可以得到的
第三个证明呢？我们在原式两边同时卷上一个I ，就得到
\varphi \times I = \mu \times \varepsilon \times I
根据前两个式子，我们可以得到
\varepsilon = e \times \varepsilon
根据原函数e 的定义，任何数论函数卷e 都等于自己
所以这个式子是成立的
根据以上的定义，我们已经可以做莫比乌斯反演了
莫比乌斯反演
本质：
这里列举两个套路：
[gcd(i,j) == 1] = \sum_{d|gcd(i,j)}\mu(d) \space \Leftrightarrow \space \mu \times I = e
[gcd(i,j)] = \sum_{d|gcd(i,j)}\varphi(d) \space \Leftrightarrow \space \varepsilon = \varphi \times I
这两个的套路是根据狄利克雷卷积的性质，将gcd(i,j) 当做n 带入即可
就这么简单
怎么求出\mu
前面我们已经说过了，\mu 是一个积性函数，所以我们可以用线性筛求出来
我们分析一下，对于一个质数p ：
质数p 只有一个质因子（他自己本身），\mu(p) = -1
当i\% p != 0 时，根据积性函数定义，\mu(i\times p) = - \mu(i)
当i\% p == 0 时，i\times p 有平方因子，\mu(i\times p) = 0
inline void GetMiu(int n) {
vis[0] = vis[1] = true; mu[1] = 1;
for(R int i=2; i<=n; i++) {
if(!vis[i]) pri[++tot] = i , mu[i] = -1;
for(R int j=1; j<=tot&&i*pri[j]<=n; j++) {
vis[i*pri[j]] = true;
if(i%pri[j]) mu[i*pri[j]] = -mu[i];
else { mu[i*pri[j]] = 0; break; }
}
}
}讲了这么多，我们来做几道题练练手吧
洛谷P2522 [HAOI2011]Problem b
题目大意：求当 i \in [a,b] , j \in [c,d] ，满足gcd(i,j) = k 的数对(i,j) 的个数
推莫比乌斯反演的时候，不要慌，先把式子列出来再说
另题目所求的答案 = ans ，则
ans = \sum_{i=a}^{b}\sum_{j=c}^{d}[gcd(i,j)==k]
首先我们来定义一个函数f ，f(n,m) = \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==k]
那么这个ans 显然可以容斥对吧
那么ans = f(c,d) - f(a-1,d) - f(b,c-1) + f(a-1,c-1)
懂了吗？？？肯定懂了！
如果你还不懂的话，把这个问题理解为：
你有一个b\times d 的矩形，求右下角那个(b-a+1)\times (d-c+1) 的矩形面积
然后题目的答案显然是：
现在懂了吧
于是我们只需要求f(n,m) 就行了，到时候a,b,c,d 什么的分别当做n,m 带入就行了
f(n,m) = \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==k]
首先，我们知道，如果gcd(i,j) == k ，那么gcd(\frac{i}{k},\frac{j}{k}) == 1 （这是一个定理，背背背背背背）
这说明了i,j 一定是k 的倍数，那么我们不妨设i=k\times x , j = k \times y （这里采用了换元的思想）
则：f(n,m) = \sum_{kx=1}^{n}\sum_{ky=1}^{m}[gcd(kx,ky)==k]
化简一下：f(n,m) = \sum_{x=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{y=1}^{\lfloor \frac{m}{k} \rfloor}[gcd(x,y)==1]
哇，看着x,y 不舒服，我们还是把i,j 换回来吧，当然此i,j 非一开始的那个i,j
f(n,m) = \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[gcd(i,j)==1]
看到[gcd(i,j)==1] ，我们立马转莫比乌斯函数\mu
f(n,m) = \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d|gcd(i,j)}\mu(d)
这里提一下，d|gcd(i,j) = d|i 并且 d|j
我们把这个d 给提到前面去
f(n,m) = \sum_{d=1}^{min(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{m}{k} \rfloor)}\mu(d)\sum_{d|i}^{\lfloor \frac{n}{k} \rfloor}\sum_{d|j}^{\lfloor \frac{m}{k} \rfloor}
我们可以发发现，对于d|i , d|j ，我们依旧可以还原，枚举id,jd ，于是原式又变成了
f(n,m) = \sum_{d=1}^{min(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{m}{k} \rfloor)}\mu(d)\sum_{id}^{\lfloor \frac{n}{k} \rfloor}\sum_{jd}^{\lfloor \frac{m}{k} \rfloor}
化简一下
f(n,m) = \sum_{d=1}^{min(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{m}{k} \rfloor)}\mu(d)\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{kd} \rfloor}
f(n,m) = \sum_{d=1}^{min(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{m}{k} \rfloor)}\mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor
这就是最终式子了
至于这个式子，将\mu 做一个前缀和，利用数论分块的思想来做
inline int Mobius(int n , int m , int k) {
if(n > m) swap(n,m);
n /= k , m /= k; R int ans = 0;
for(R int i=1; i<=n; i=j+1) {
i = min( n / (n/i) , m / (m/i) );
ans += ( SumMu[j] - SumMu[i-1] ) * ( n / i ) * ( m / i );
}
return ans;
}时间复杂度是O(\sqrt{n}) 的，我们就可以愉快的满足那险恶的T 组询问了
怎么样，代码就这么短，就是这么好写
洛谷P1829 [国家集训队]Crash的数字表格 / JZPTAB
题目大意：求\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)
这道题的详解，我以前已经写过一次了
没看过的可以戳下面qwq
传送门
我在这里就简单的把式子列出来一下吧
lcm(i,j) = \frac{ij}{gcd(i,j)}
ans = \sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)
\space \space \space \space \space \space \space = \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)}
\space \space \space \space \space \space \space = \sum_{d=1}^{min(n,m)}\frac{1}{d}\sum_{d|i}\sum_{d|j}i\times j[gcd(i,j)==d]
\space \space \space \space \space \space \space = \sum_{d=1}^{min(n,m)}\frac{1}{d}\sum_{id=1}^{n}\sum_{jd=1}^{m}id\times jd[gcd(id,jd)==d]
\space \space \space \space \space \space \space = \sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}i\times j[gcd(i,j)==1]
\space \space \space \space \space \space \space = \sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}i\times j\sum_{p|i,j}\mu(p)
\space \space \space \space \space \space \space = \sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(p)\sum_{p|i}\sum_{p|j}i\times j
\space \space \space \space \space \space \space = \sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(p)\sum_{ip=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{jp=1}^{\lfloor \frac{m}{d} \rfloor}ip\times jp
\space \space \space \space \space \space \space = \sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(p)p^{2}\times \sum_{i=1}^{\lfloor \frac{n}{dp} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{dp} \rfloor}i\times j
\space \space \space \space \space \space \space = \sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(p)p^{2}\times \sum_{i=1}^{\lfloor \frac{n}{dp} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{dp} \rfloor}j
\space \space \space \space \space \space \space = \sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(p)p^{2}\times Sum(\lfloor \frac{n}{dp} \rfloor)\times Sum(\lfloor \frac{m}{dp} \rfloor)
其中Sum(x) = \sum_{i=1}^{x}i = \frac{x*(x+1)}{2} ，等差数列求和，可以O(1) 算
到这里式子就推完了，前半部分分块，后半部分也分块，时间复杂度 = O(\sqrt{n}) \times O(\sqrt{n}) = O(n)
然后我们重新考虑一个问题
如果我们把这个题目改成有Q 组询问，1 \leq Q \leq 5 \times 10^{4} 呢？
显然，O(Qn) 是过不去的，我们需要对这个式子再做一次反演
我们设 T = d\times p ，那我们把T 提到前面来，只枚举T 和p ，d 可以表示为\frac{T}{p}
ans = \sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(p)p^{2}\times Sum(\lfloor \frac{n}{dp} \rfloor)\times Sum(\lfloor \frac{m}{dp} \rfloor)
\space \space \space \space \space \space \space = \sum_{T=1}^{min(n,m)}Sum(\lfloor \frac{n}{T} \rfloor)\times Sum(\lfloor \frac{m}{T} \rfloor)\sum_{p|T}\mu(p)p^{2}\times \frac{T}{p}
\space \space \space \space \space \space \space = \sum_{T=1}^{min(n,m)}Sum(\lfloor \frac{n}{T} \rfloor)\times Sum(\lfloor \frac{m}{T} \rfloor)T\sum_{p|T}\mu(p)p
设g(T) = \sum_{p|T}\mu(p)p
我们发现，g 是一个积性函数，可以用线性筛筛出来
怎么线筛呢？
对于质数p
g(p)= \mu(1)*1 + \mu(p)*p = 1 - p
当i \% p !=0 时，根据积性函数的性质，g(i\times p) = g(i) \times g(p)
当i \% p == 0 时，对于i*p 这个数，除了拥有i 的约数，其他的所有约数必定包含有p 的平方因子，这些因子的\mu 都是0 ，所以g(i\times p) = g(i)
inline void GetF(int n) {
f[1] = 1 , vis[0] = vis[1] = true;
for(R int i=2; i<=n; i++) {
if(!vis[i]) f[i] = 1 - i , pri[++tot] = i;
for(R int j=1; j<=tot&&i*pri[j]<=n; j++) {
vis[i*pri[j]] = true;
if(i%pri[j]) f[i*pri[j]] = f[i] * f[pri[j]];
else { f[i*pri[j]] = f[i]; break; }
}
}
}这样子整个式子只用分块一次，时间复杂度就是O(\sqrt{n}) ，可以处理Q 组询问了
洛谷P3768 简单的数学题
zzq出的题，快\% 快\%
题目大意：求\sum_{i=1}^{n}\sum_{j=1}^{m}ijgcd(i,j) 的值
对于这道题我们考虑另一种反演方式
我们不用\mu ，我们用\varphi
根据\varepsilon = \varphi \times I ，我们大力推一波式子：
ans = \sum_{i=1}^{n}\sum_{j=1}^{n}ijgcd(i,j)
\space \space \space \space \space \space \space = \sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{d|i,j}\varphi(d)
\space \space \space \space \space \space \space = \sum_{d=1}^{n}\varphi(d)\sum_{d|i}\sum_{d|j}ij
\space \space \space \space \space \space \space = \sum_{d=1}^{n}\varphi(d)\sum_{id=1}^{n}\sum_{jd=1}^{n}idjd
\space \space \space \space \space \space \space = \sum_{d=1}^{n}\varphi(d)d^{2}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}j
\space \space \space \space \space \space \space = \sum_{d=1}^{n}\varphi(d)d^{2}(\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i)^{2}
直接大力分块即可
然后看一下数据，woc ，n \leq 10^{10} ，GG 辣
这时我们就需要引进一个新的东西，叫做杜教筛
什么是杜教筛？
现在我们就是要求这个东西：\varphi(i)\times i^{2}
挂一下杜教筛的核心公式（全程都要用到他）：
g(1)S(n) = \sum_{i=1}^{n}(f\times g)(i) - \sum_{i=2}^{n}g(i)S(\lfloor \frac{n}{i} \rfloor)
我们设f(i) = \varphi(i) \times i^{2} ，g(i) = i^{2}
(f\times g)(i) = \sum_{d|i}f(d)g(\frac{i}{d}) = \sum_{d|i}\varphi(d)d^{2}(\frac{i}{d})^{2} = i^{2}\sum_{d|i}\varphi(d) = i^{3}
带入原式
S(n) = \sum_{i=1}^{n}i^{3} - \sum_{i=2}^{n}i^{2}S(\lfloor \frac{n}{i} \rfloor)
有个非常神奇的公式：
\sum_{i=1}^{n}i^{3} = (\sum_{i=1}^{n}i)^{2}
带入即可：
S(n) = (\sum_{i=1}^{n}i)^{2} - \sum_{i=2}^{n}i^{2}S(\lfloor \frac{n}{i} \rfloor)
这样就可以求解了
inline LL SqrSum(LL x) { x %= Mod; return x * (x+1) % Mod * (x+x+1) % Mod * InvSix % Mod; }
inline LL Phi(LL n) {
if(n <= Maxn-10) return f[n];
if(m.count(n)) return m[n];
R LL ans = Sqr(Sum(n));
for(R LL i=2,j; i<=n; i=j+1) {
j = n / ( n / i );
ans = ( ans - ( SqrSum(j) - SqrSum(i-1) + Mod ) % Mod * Phi(n/i) % Mod + Mod ) % Mod;
}
return m[n] = ans;
}