首页 > 其他分享 >莫比乌斯函数及其反演

莫比乌斯函数及其反演

时间：2025-01-16 16:35:41浏览次数：1  
标签：lfloor frac int 乌斯 sum rfloor mu 反演 莫比

一些定义

数论函数
定义域为正整数的函数，一般分类如下：

  1. 积性函数
    对于 \(\forall x,y \in N , gcd(x,y)=1\) ，若 \(f(x \cdot y)=f(x) \cdot f(y)\) ，则 \(f\) 是积性函数。
  2. 完全积性函数
    对于 \(\forall x,y \in N\) ，若 \(f(x \cdot y)=f(x) \cdot f(y)\) ,则 \(f\) 是完全积性函数。
  3. 非积性函数

狄利克雷卷积
可以理解为数论函数的乘法，常用符号 \(*\) 表示。
若 \(f,g\) 均为数论函数，则有 \((f*g)(n) = \sum_{d|n}f(d)g(\frac{n}{d})\) 。
对于数论函数乘法，其单位元函数为 \(e\) ：

\[e(n) = \begin{cases} 1\ , n=1 \\ 0\ , n \ne 1 \end{cases} \]

即对于任意数论函数 \(f\) ,都有 \(f*e=f\) 。
狄利克雷卷积满足交换律和结合律。

莫比乌斯函数

莫比乌斯函数 \(\mu\) 的定义如下：

\[\mu(n) = \begin{cases} 1\ , n=1 \\ 0\ , n包含平方因数 \\ (-1)^k\ ,k为n的本质不同质因子个数 \end{cases} \]

\(\mu\) 是积性函数。

性质：

  1. \(\forall n \in N , \sum_{d|n}\mu(d) = [n=1]\)
    莫比乌斯反演中最常用的性质。
    推论：\(e(n) = \sum_{d|n}\mu(d) \Rightarrow e(n) = \sum_{d|n}\mu(d)1(\frac{n}{d}) \Rightarrow e=\mu*1\)
  2. \(\forall n \in N , \sum_{d|n}\frac{\mu(d)}{d} = \frac{\phi(n)}{n}\)

求莫比乌斯函数：
由于 \(\mu\) 是积性函数，所以 \(\mu\) 可以像素数一样筛出来。
下面给出线性筛法：

void init(){
    memset(is_prime,1,sizeof is_prime);
    is_prime[1]=0; mu[1]=1;
    for (int i=2;i<=MAXN;i++){ //这里的MAXN注意边界
        if (!is_prime[i]) continue;
        prime[++cnt]=i;
        for (int j=1;j<=cnt&&1ll*i*prime[j]<=MAXN;j++){
            is_prime[i*prime[j]]=0;
            if (i%prime[j]==0) break; // mu在这个位置上本来就是0，不用额外赋值
            mu[i*prime[j]]=-mu[i]; // 质因子数+1，mu乘上-1
        }
    }
    return;
}

莫比乌斯反演

\[\textstyle g(n) = \sum_{d|n}f(d) \;\Leftrightarrow\; f(n) = \sum_{d|n}g(d)\mu(\frac{n}{d}) \]

证明：
由性质一我们已知 \(e=\mu*1\) ，
而 \(g(n) = \sum_{d|n}f(d) \;\Rightarrow\; g(n) = \sum_{d|n}f(d)1(\frac{n}{d}) \;\Rightarrow\; g=f*1\) ，
将等式两边同乘 \(\mu\) ， \(g*\mu=f*(1*\mu) \;\Rightarrow\; g*\mu=f*e \;\Rightarrow\; f=g*\mu\) ，
于是 \(g(n) = \sum_{d|n}f(d) \;\Rightarrow\; f(n) = \sum_{d|n}g(d)\mu(\frac{n}{d})\) ，反之亦然。

例题（莫比乌斯函数及性质）

P3455 [POI2007] ZAP-Queries

给出 \(a,b,d\)，求满足 \(1 \leq x \leq a\)，\(1 \leq y \leq b\)，且 \(\gcd(x,y)=d\) 的二元组 \((x,y)\) 的数量。
DATA：\(1 \leq n \leq 5 \times 10^4\)，\(1 \leq d \leq a,b \leq 5 \times 10^4\)。
Solution
答案可记作 \(Ans = \sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}[\gcd(x,y)=d]\) （\(a\leq b\)）
\(\because \gcd(\alpha,\beta)=1 \;\Rightarrow\; \gcd(\alpha c,\beta c)=c\)
\( \begin{aligned} \therefore Ans &= \textstyle\sum\limits_{i=1}^{\lfloor\frac{a}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{b}{d}\rfloor}[\gcd(x,y)=1]\\ &= \textstyle\sum\limits_{i=1}^{\lfloor\frac{a}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{b}{d}\rfloor}\sum_{d'|\gcd(x,y)}\mu(d') （性质一）\\ &= \textstyle\sum\limits_{d'=1}^{\lfloor\frac{a}{d}\rfloor}\mu(d')\lfloor\frac{\lfloor\frac{a}{d}\rfloor}{d'}\rfloor\lfloor\frac{\lfloor\frac{b}{d}\rfloor}{d'}\rfloor （枚举d'，交换求和顺序） \end{aligned} \)
由此复杂度可降至 \(O(na)\) ，但依旧不足以通过此题。
考虑数论分块，也就是把 \(\lfloor\frac{\lfloor\frac{a}{d}\rfloor}{d'}\rfloor\lfloor\frac{\lfloor\frac{b}{d}\rfloor}{d'}\rfloor\) 相同的项合并起来算，乘与 \(\sum\limits_{d'=start}^{end}\mu(d')\) 即可，这部分用前缀和。

Code 
#include <bits/stdc++.h>
#define MAXN 100003
using namespace std;
int T;
int x,y,d;
int is_prime[MAXN];
int prime[MAXN]; int cnt;
int mu[MAXN];
long long sum[MAXN];
void init(){
    for (int i=1;i<=MAXN-2;i++) is_prime[i]=1;
    is_prime[1]=0; is_prime[2]=1; mu[1]=1;
    for (int i=2;i<=MAXN-2;i++){ // 数据范围不大，这里是nlogn筛
        if (!is_prime[i]) continue;
        mu[i]=-1;
        int j=2;
        while (1ll*i*j<=MAXN-2){
            is_prime[i*j]=0;
            if (j%i==0) mu[i*j]=0;
            else mu[i*j]=mu[i]*mu[j];
            j++;
        }
    }
    for (int i=1;i<=MAXN-2;i++) if (is_prime[i]) prime[++cnt]=i;
    for (int i=1;i<=MAXN-2;i++) sum[i]=sum[i-1]+mu[i];
    return;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    init();
    cin>>T;
    while (T--){
        cin>>x>>y>>d;
        int N=x/d,M=y/d;
        long long ans=0;
        for (int d2=1;d2<=min(N,M);d2++){
            int nxt=min(N/(N/d2),M/(M/d2));
            ans+=1ll*(sum[nxt]-sum[d2-1])*(N/d2)*(M/d2);
            d2=nxt;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

P2522 [HAOI2011] Problem b

对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a \le x \le b\)，\(c \le y \le d\)，且 \(\gcd(x,y) = k\)，\(\gcd(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。
DATA：\(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\)。
Solution
与上题相似，加一个容斥即可。

Code 
#include <bits/stdc++.h>
#define MAXN 100003
using namespace std;
int T;
int a,b,c,d,k;
int is_prime[MAXN];
int prime[MAXN]; int cnt;
int mu[MAXN];
long long sum[MAXN];
void init(){
    for (int i=1;i<=MAXN-2;i++) is_prime[i]=1;
    is_prime[1]=0; is_prime[2]=1; mu[1]=1;
    for (int i=2;i<=MAXN-2;i++){ //数据范围小我就不用线性筛
        if (!is_prime[i]) continue;
        mu[i]=-1;
        int j=2;
        while (1ll*i*j<=MAXN-2){
            is_prime[i*j]=0;
            if (j%i==0) mu[i*j]=0;
            else mu[i*j]=mu[i]*mu[j];
            j++;
        }
    }
    for (int i=1;i<=MAXN-2;i++) if (is_prime[i]) prime[++cnt]=i;
    for (int i=1;i<=MAXN-2;i++) sum[i]=sum[i-1]+mu[i];
    return;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    init();
    cin>>T;
    while (T--){
        cin>>a>>b>>c>>d>>k;
        int N=b/k,M=d/k;
        long long ans1=0,ans2=0,ans3=0,ans4=0;
        for (int d2=1;d2<=min(N,M);d2++){
            int nxt=min(N/(N/d2),M/(M/d2));
            ans1+=1ll*(sum[nxt]-sum[d2-1])*(N/d2)*(M/d2);
            d2=nxt;
        }
        N=(a-1)/k; M=d/k;
        for (int d2=1;d2<=min(N,M);d2++){
            int nxt=min(N/(N/d2),M/(M/d2));
            ans2+=1ll*(sum[nxt]-sum[d2-1])*(N/d2)*(M/d2);
            d2=nxt;
        }
        N=(c-1)/k; M=b/k;
        for (int d2=1;d2<=min(N,M);d2++){
            int nxt=min(N/(N/d2),M/(M/d2));
            ans3+=1ll*(sum[nxt]-sum[d2-1])*(N/d2)*(M/d2);
            d2=nxt;
        }
        N=(a-1)/k; M=(c-1)/k;
        for (int d2=1;d2<=min(N,M);d2++){
            int nxt=min(N/(N/d2),M/(M/d2));
            ans4+=1ll*(sum[nxt]-sum[d2-1])*(N/d2)*(M/d2);
            d2=nxt;
        }
        cout<<ans1-ans2-ans3+ans4<<'\n';
    }
    return 0;
}

P2257 YY的GCD

给定 \(N, M\)，求 \(1 \leq x \leq N\)，\(1 \leq y \leq M\) 且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对。
DATA：\(T = 10^4\)，\(N, M \leq 10^7\)。
Solution
只需要稍微退推一下柿子（，
令 \(N \leq M\) ，
\( \begin{aligned} Ans &= \textstyle\sum\limits_{p \in prime}^{N}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}[\gcd(i,j)=p]\\ &= \textstyle\sum\limits_{p \in prime}^{N}\sum\limits_{i=1}^{\lfloor\frac{N}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{M}{p}\rfloor}[\gcd(i,j)=1] \\ &= \textstyle\sum\limits_{p \in prime}^{N}\sum\limits_{i=1}^{\lfloor\frac{N}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{M}{p}\rfloor}\sum_{d|\gcd(i,j)}\mu(d) \\ &= \textstyle\sum\limits_{p \in prime}^{N}\sum\limits_{d=1}^{\lfloor\frac{N}{p}\rfloor}\mu(d)*\lfloor\frac{N}{pd}\rfloor*\lfloor\frac{M}{pd}\rfloor \\ \end{aligned} \)
设 \(T=pd\) ， \(d=\frac{T}{p}\) ：
\( \begin{aligned} Ans &= \textstyle\sum\limits_{p \in prime}^{N}\sum\limits_{d=1}^{\lfloor\frac{N}{p}\rfloor}\mu(\frac{T}{p})*\lfloor\frac{N}{T}\rfloor*\lfloor\frac{M}{T}\rfloor \\ &= \textstyle\sum\limits_{T=1}^{N}\lfloor\frac{N}{T}\rfloor\lfloor\frac{M}{T}\rfloor\sum\limits_{p|T,p \in prime}\mu(\frac{T}{p}) （枚举T，交换求和顺序） \\ \end{aligned} \)
这下前面一部分可以用数论分块做，后半部分枚举 \(p\) 计算对 \(T\) 的贡献即可。
时间复杂度 \(O(n+T\sqrt{n})\)

Code 
#include <bits/stdc++.h>
#define MAXN 10000003
using namespace std;
int T;
int n,m;
int is_prime[MAXN],prime[MAXN],cnt;
int mu[MAXN],sum[MAXN];
long long f[MAXN],sumf[MAXN];
void init(){
    for (int i=2;i<=MAXN-2;i++) is_prime[i]=1;
    mu[1]=1;
    for (int i=2;i<=MAXN-2;i++){ //nlogn筛似了，换成线性筛
        if (is_prime[i]){
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for (int j=1;j<=cnt&&1ll*i*prime[j]<=MAXN-2;j++){
            is_prime[i*prime[j]]=0;
            if (i%prime[j]==0) break;
            mu[i*prime[j]]=-mu[i];
        }
    }
    for (int i=1;i<=MAXN-2;i++) sum[i]=sum[i-1]+mu[i];
    for (int i=1;i<=cnt;i++){
        for (int j=1;j<=MAXN-2&&1ll*prime[i]*j<=MAXN-2;j++){ //计算质数p对T的贡献
            f[prime[i]*j]+=mu[j];
        }
    }
    for (int i=1;i<=MAXN-2;i++) sumf[i]=sumf[i-1]+f[i];
    return;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    init();
    cin>>T;
    while (T--){
        cin>>n>>m;
        if (n>m) swap(n,m);
        long long ans=0;
        for (int T=1;T<=n;T++){
            int nxt=min(n/(n/T),m/(m/T));
            ans+=1ll*(n/T)*(m/T)*(sumf[nxt]-sumf[T-1]);
            T=nxt;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

例题（真正的莫比乌斯反演）

P5518 [MtOI2019] 幽灵乐团 / 莫比乌斯反演基础练习题

\[\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)} (mod\ p) \]

\[\begin{aligned} f(0)&=1 \cr f(1)&=i \times j \times k \cr f(2)&=\gcd(i,j,k) \end{aligned}\]

DATA：$$ 1\leq A,B,C\leq 10^5 \ \ \ \ 10^7 \leq p \leq 1.05\times 10^9\ \ \ \ p\in { prime} \ \ \ \ T =70$$
咕

其它东西

题单

莫比乌斯反演（函数）练习题单

参考资料

【数论】莫比乌斯函数/莫比乌斯反演
数论小白入门-- 莫比乌斯反演
【数论】莫比乌斯函数及其反演
莫比乌斯函数
关于n，欧拉函数与莫比乌斯函数的互化

标签：lfloor,frac,int,乌斯,sum,rfloor,mu,反演,莫比
From： https://www.cnblogs.com/MoCy233/p/18675223

相关文章

  • 【学习笔记】【数论】欧拉函数&莫比乌斯函数及反演
    一、欧拉函数1.欧拉函数的意义\(\phi(n)\)表示从\(1\)到\(n\)所有与\(n\)互质的数的数量。表达式为：\(\sum\limits_{i=1}^{n}[\gcd(i,n)=1]\)。2.欧拉函数的通解公式\(\phi(n)=n\prod\limits_{i=1}^{k}(1-\frac{1}{p^i})\)（\(p_i\midn\)，\(p_i\)为素数，\(k\)为小于等于......
  • 二项式反演和容斥原理学习笔记
    容斥原理先从容斥原理开始。容斥原理的结论如下：$$|\bigcup\limits_{i=1}^{n}S_{i}|=\sum\limits_{m=1}{n}(-1)\sum\limits_{a_{i}<a_{i-1}}|\bigcap_{i=1}^{m}S_{a_{i}}|$$证明的思路是考虑一个元素在每一个$\bigcap\limits_{i=1}^{m}S_{a_{i}}$里出现的次......
  • [学习笔记] 二项式定理与反演
    一假设\(f(x)\)代表恰好满足\(x\)个性质的方案数。钦定代表至少\(x\)个。假设\(g(x)\)代表至多满足\(x\)个性质的方案数。显然有\[g(n)=\sum_{i=0}^n\left(\begin{matrix}n\\i\end{matrix}\right)f(i)\]并且有\[f(n)=\sum_{i=0}^n\left(\begin{matrix}n\\i\end{ma......
  • 莫比乌斯反演学习笔记
    前置知识一、整除分块即按照\(\lfloor\frac{n}{i}\rfloor\)的值域进行分块，块数$\leq\lfloor2\sqrtn\rfloor$。分$i\leq\lfloor\sqrtn\rfloor$，$i>\lfloor\sqrtn\rfloor$讨论。\(i\)所在块的右端点为$\lfloor\frac{n}{\lfloor\frac{n}{i}\rfl......
  • 反演笔记
    反演反演若已知\(f(n)=\sumg(k)\)，用\(f\)表示\(g\)的过程就叫“反演”。二项式反演参考一下邓老师的PPT。经典题：\(n\)个元素错排的方案数。要求线性。考虑枚举有\(k\)个人非错排，可以得到这\(k\)个人一共有\(\dbinom{n}{k}\)种选法，剩下的人有\((n-k)\)......
  • 人工智能原理期末速成——消解反演与反演求解
    消解反演：证明真或假反演求解：求解变量值消解反演解法：1.否定命题，将否定后的命题加入前提2.通过前提之间互相组合，得到新的前提3.最终前提与前提互相矛盾，得到NIL，此时证明完成注：在第1步之后第2步之前，还需要将所有的命题转换成子句形式例1：设已知：（1）能阅读的人是识字的（2）海豚不......
  • 遥感技术在生态系统碳储量、碳收支、碳循环以及人为源排放反演等领域的技术发展
    以全球变暖为主要特征的气候变化已成为全球性环境问题，对全球可持续发展带来严峻挑战。2015年多国在《巴黎协定》上明确提出缔约方应尽快实现碳达峰和碳中和目标。2019年第49届 IPCC全会明确增加了基于卫星遥感的排放清单校验方法。随着碳中和目标以及全球碳盘点的现实压力，基于......
  • 子集反演 & sos dp 学习笔记
    子集反演&sosdp学习笔记子集反演设\(g(S)\)表示集合\(S\)的答案，\(f(S)\)为\(S\)的子集的答案和。根据定义：\[f(S)=\sum_{T\inS}g(T)\]子集反演就是：\[g(S)=\sum_{T\inS}(-1)^{|S|-|T|}f(T)\]本质上就是容斥原理，可感性理解，证明略（给你你也记不住）。于是便可以通......
  • 数论 莫比乌斯反演
    前置需求数论分块概念对于一个形如\(\sum_{x=1}^n\lfloor{\frac{n}{x}}\rfloor\)的式子，我们发现对于一部分的\(x\)，它们的\(\lfloor{\frac{n}{x}}\rfloor\)值相同，因此我们没必要\(\mathcal{O(n)}\)计算，可以采用数论分块的办法将这一步的复杂度降低至\(\mathcal{O(\sqrt......
  • 二项式反演学习笔记
    前言万字长文！这里有我的一些思考和领会，网络上的教程都太潦草了。并且我发现了新的反演公式！概述二项式反演用于转化两个具有特殊关系的函数\(f\)和\(g\)，从而方便求解问题。一般来说，直接计算恰好满足\(n\)个限制的答案不好求，但是可以计算出“至少”/“至多”满足\(n\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99