当前位置:首页 >> 学科竞赛 >> 莫比乌斯反演

莫比乌斯反演


莫比乌斯反演
——吉大附中实验学校 PoPoQQQ

什么是莫比乌斯反演?
? 介绍这个之前,我们先来看一个函数 ? F (n) ? f (d )

?
d |n

? ? ? ? ? ? ? ? ?

根据F(n)的定义,我们显然有: F(1)=f(1) F(2)=f

(1)+f(2) F(3)=f(1)+f(3) F(4)=f(1)+f(2)+f(4) F(5)=f(1)+f(5) F(6)=f(1)+f(2)+f(3)+f(6) F(7)=f(1)+f(7) F(8)=f(1)+f(2)+f(4)+f(8)

于是我们可以通过F(n)推导出f(n)
? ? ? ? ? ? ? ? ? f(1)=F(1) f(2)=F(2)-F(1) f(3)=F(3)-F(1) f(4)=F(4)-F(2) f(5)=F(5)-F(1) f(6)=F(6)-F(3)-F(2)+F(1) f(7)=F(7)-F(1) f(8)=F(8)-F(4) 在推导的过程中我们是否发现了一些规律?

莫比乌斯反演
? 公式:
n F (n) ? ? f (d ) ? f (n) ? ? ? (d )F ( ) d d |n d |n

? ? ? ?

其中 ? ( d )为莫比乌斯函数,定义如下: (1)若 d ? 1则 ? (d ) ? 1 k ? ( d ) ? ( ? 1) pi 为互异素数,那么 (2)若 d ? p1 p2 ... pk , (3)其它情况下 ? (d ) ? 0

莫比乌斯函数的性质
? (1)对于任意正整数n有:

?1 ? (d ) ? ? ? d |n ?0

( n ? 1) (n ? 1)

? 证明: ? ①当 n ? 1时显然 ak a1 a2 ? ②当 n ? 1时,将 n 分解可以得到 n ? p1 p2 ... pk ? 值不为零的只有所有质因子次数都 ? 在 n 的所有因子中, r 为1的因子,其中质因数个数为 r 个的因子有 Ck 个 ? 那么显然有: k
0 1 2 k k i i ? ( d ) ? C ? C ? C ? ... ? ( ? 1) C ? ( ? 1) ? ? Ck k k k k d |n i ?0

莫比乌斯函数的性质
i i ( ? 1) Cn ? 0 ( n ? N ? ) 即可 ? 只需证明 ? i ?0 n

i i n ?i ( x ? y ) ? C ? nx y ? 二项式定理: i ?0 n

n

? 令 x ? ?1, y

?1 ,代入即可得证。

莫比乌斯函数的性质
? (2)对于任意正整数n有: ? ( d ) ? ( n) ? ? d n d |n ? 其实没什么用,结论挺好玩的可以记一下 ? 只需要令 F (n) ? n, f (n) ? ? (n) ,代入莫比乌斯反演的公 式即可 ? (d )就留给大家做思考题了 ? 至于为什么 n ?

?
d |n

莫比乌斯函数的性质
? (3)积性函数 ? 数论上积性函数的定义:

设f (n)为一个定义在N ? 集合上的函数,如果对于 任意( x, y ) ? 1有f ( xy ) ? f ( x) f ( y ),则称f (n)为一个 积性函数;若对于任意x和y均有f ( xy ) ? f ( x) f ( y ), 则称f (n)为一个完全积性函数
? 积性函数的性质: ? ① f (1) ? 1 ? ②积性函数的前缀和也是积性函数

莫比乌斯函数的性质
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 由于莫比乌斯函数是积性函数,因此我们可以通过线性筛来求出莫比乌斯函数的值 代码: mu[1]=1; for(i=2;i<=n;i++) { if(!not_prime[i]) { prime[++tot]=i; mu[i]=-1; } for(j=1;prime[j]*i<=n;j++) { not_prime[prime[j]*i]=1; if(i%prime[j]==0) { mu[prime[j]*i]=0; break; } mu[prime[j]*i]=-mu[i]; } }

BZOJ 2440 完全平方数
? 题目大意:求第k个无平方因子数 ? 无平方因子数(Square-Free Number),即分解之后所有质 因数的次数都为1的数 ? 首先二分答案 问题转化为求[1,x]之间有多少个无平方因子 数 ? 根据容斥原理可知 对于sqrt(x)以内所有的质数 有 ? x以内的无平方因子数 ? =0个质数乘积的平方的倍数的数的数量(1的倍数) ? -每个质数的平方的倍数的数的数量(9的倍数,25的倍数,...) ? +每2个质数乘积的平方的倍数的数的数量(36的倍数,100 的倍数,...)-...

BZOJ 2440 完全平方数
? 容易发现每个乘积a前面的符号恰好是 ? ( a ) (例如 ? (3) ? ?1, 故9对答案的贡献为负;? (6) ? 1 ,故36对答案的贡献为正 ? x? ? ? ) ?x? ?x? Q( x) ? ? (i ) ? 2 ? 2? ? ?i ? ?i ? i ?1 ? x以内i^2的倍数有 个 故有 ? 这题和莫比乌斯反演没关系,算是莫比乌斯函数的一个应 用吧。。。

?

现在我们来证明莫比乌斯反演定理
n F (n) ? ? f (d ) ? f (n) ? ? ? (d )F ( ) d d |n d |n

? 证明:
n f ( n ) ? ? ? ( d ) F ( ) ? ? ? ( d ) ? f ( k ) ? ? f ( k ) ? ? ( d ) ? f ( n) d n n d |n d |n k |n k| d|
d k

? 这里利用到了 ? ? (d ) ? ?0
d |n

?1 ?

(n ? 1) (n ? 1) 这条性质

d F ( n ) ? f ( d ) ? f ( n ) ? ? ( )F (d ) ? 形式二: ? ? n n|d n|d

? 证明同理 一般要用到的都是这种形式

有了这个定理,我们能干什么?
? 对于一些函数f(n),如果我们很难直接求出它的值,而容 易求出倍数和或约数和F(n),那么我们可以通过莫比乌斯 反演来求得f(n)的值 ? 例:f(n)表示某一范围内(x,y)=n的数对的数量,F(n)表示 某一范围内n|(x,y)的数对的数量 ? 那么直接求f(n)并不是很好求,而F(n)求起来相对无脑一 些,我们可以通过对F(n)进行莫比乌斯反演来求得f(n) ? 下面用几道例题来为大家讲解一下莫比乌斯反演的好处

BZOJ 2301 Problem b
? n次询问,每次询问有多少个数对(x,y)满足 a<=x<=b,c<=y<=d且gcd(x,y)=k ? N<=5W,1<=a<=b<=5W,1<=c<=d<=5W ? 首先利用容斥原理将一个询问拆分成四个,每次询问有多 少个数对(x,y)满足1<=x<=n,1<=y<=m且gcd(x,y)=k ? 这个问题等价于询问有多少个数对(x,y)满足 1<=x<=floor(n/k),1<=y<=floor(m/k)且x与y互质 ? 利用NOI2010能量采集中的方法,我们可以得到一个 O(nlogn)的算法,但是这显然不能胜任此题的数据范围 ? 这时候我们就可以考虑莫比乌斯反演了

BZOJ 2301 Problem b
? 由于之前的结论,我们可以令f(i)为1<=x<=n,1<=y<=m且 gcd(x,y)=i的数对(x,y)的个数,F(i)为1<=x<=n,1<=y<=m且 i|gcd(x,y)的数对(x,y)的个数

?n? ?m? F (i) ? ? ? ? ? ? 那么显然有 ?i ?? i ? d d ? n ? ?m? f (i) ? ? ? ( )F (d ) ? ? ? ( ) ? ? ? ? ? 反演后可得 i i ?d ? ? d ? i| d i| d
? 枚举原题中k的每一个倍数,我们就可以O(n)时间处理每 个询问了 ? 但是O(n)还是不能胜任本题的数据范围 ? 考虑进一步优化

BZOJ 2301 Problem b
?n? ? ? d ? 观察式子,发现 ? ? 最多有 2 n 个取值 ? n ? ?m? ? ? ? d d ? 那么 ? ? ? ? ? 就至多有 2( n ? m ) 个取值 ? 枚举这 2( n ? m )个取值,对莫比乌斯函数维护一个前缀

和,就可以在 ?( n )时间内出解 ? 总时间复杂度?(n n ) ? 枚举除法的取值这种方法在莫比乌斯反演的应用当中非常 常用,且代码并不难写 ? 不难写?怎么写?

BZOJ 2301 Problem b
? ? ? ? ? ? ? ? if(n>m) swap(n,m); for(i=1;i<=n;i=last+1) { last=min(n/(n/i),m/(m/i)); re+=(n/i)*(m/i)*(sum[last]-sum[i-1]); } return re; 超级好写不是么?

BZOJ 2820 YGY的GCD
? 题目大意:求有多少数对(x,y)(1<=x<=n,1<=y<=m)满足 gcd(x,y)为质数 ? n,m<=1000W 数据组数<=1W ? 首先我们枚举每一个质数 那么答案就是

ans ?

min( n , m ) min( n , m )

? ?
p d ?1

? n ?? m ? ? (d ) ? ? ? ? ? pd ? ? pd ?

? 直接做显然TLE 考虑优化 ? 令pd ? T,那么有

ans ?

min( n , m )

?
T ?1

T ? n ? ?m? ?( ) ? ? ? ? ? p ? T ? ? T ? p|T

BZOJ 2820 YGY的GCD
T ?( ) ? p 的前缀和,这个问题就能在 ?( n ) ? 如果能求出 p|T
时间内出解。 ? 只需要暴力枚举每一个质数,去更新这个质数的倍数即 可。 n 1 ? 由 lim ? ln n ? r 这个结论易知每个质数更新时是均摊
n ??

?i
i ?1

?(log n)的,而质数个数恰好为?(n / log n) ? 故暴力枚举+维护前缀和的时间复杂度即为 ?( n) 。

BZOJ 3529 数表
? 题目大意:令F(i)为i的约数和,q次给定n,m,a,求
1??i ?? n 1?? j ?? m F (gcd( i , j )) ?? a

?

F (gcd(i, j )) mod 231

? ? ? ?

n,m<=10^5,q<=2W,a<=10^9 a的限制十分讨厌 我们首先假设没有这个限制 令g(i)为1<=x<=n,1<=y<=m,gcd(x,y)=i的数对(x,y)的个数 那么显然有

d ? n ? ?m? g (i) ? ? ? ( ) ? ? ? ? i ?d ? ? d ? i|d

BZOJ 3529 数表
? F(i)利用线性筛可以在O(n)时间内处理出来 那么就有
ans ?
min( n , m )

?
i ?1

F (i) g (i) ?

min( n , m )

?
i ?1

d ? n ? ? m ? min( n,m) ? n ? ? m ? d F (i)? ? ( ) ? ? ? ? ? ? ? ? ? ? ? F (i) ? ( ) i ?d ? ? d ? i i| d d ?1 ? d ? ? d ? i|d

? 治好了我多年的公式恐惧症~~ d F (i) ? ( ) ? i 的前缀和就可以在 ?( n ) 时 ? 现在我们只要有 i|d 间内解决这个弱化版的问题 ? 与上一题相同,枚举每一个i,暴力更新i的倍数,然后处 理前缀和,这样做是O(nlogn)的 ? 那么现在有了a的限制怎么搞呢?

BZOJ 3529 数表
? 我们发现对答案有贡献的i只有F(i)<=a的i ? 我们离线处理,将询问按照a排序,i按照F(i)排序 ? 每次询问将所有F(i)<=a的i按照之前的方式插入 用树状数 组维护前缀和即可 2 ? 时间复杂度 ?(n log n ? q n log n) ? 取模可以利用自然溢出int 最后再对2^31-1取与即可

BZOJ 2154 Crash的数字表格
?

i? j ans ? ?? lcm(i, j ) ? ?? i ?1 j ?1 i ?1 j ?1 gcd(i, j ) ? 枚举 d ? gcd(i, j )
n m n m

lcm(i, j ) ?? 题目大意:给定n,m,求 (n,m<=10^7)
i ?1 j ?1

n

m

? 令 F ( x, y) ?

1??i ?? x 1?? j ?? y gcd( i , j ) ?1

?

i? j

? 则有

? n ? ?m? ) min( n ,m ) min( n , m ) d ? F ( ? ? , ? ? d? ?d ? ? n ? ?m? ? ans ? ? ? ? d ? F (? ? , ? ?) d ?d ? ? d ? d ?1 d ?1
2

x( x ? 1) y( y ? 1) ? 继续令 Sum( x, y) ? ?? i ? j ? ? 2 2 i ?1 j ?1
x y

BZOJ 2154 Crash的数字表格

? 那么根据莫比乌斯反演可以推出

F ( x, y) ?

min( x , y )

?
i ?1

?x? ? y? i ? ? (i) ? Sum( ? ? , ? ?) ?i ? ?i ?
2

? 不是很好推,和之前的思路一样,我不当堂推了 ? 将两个式子分别进行 ?( n ) 的计算 可以得到一个 ?( n ? n ) ? ?(n)的算法 ? 至此本题已经可以解决。

BZOJ 2693 jzptab
? 题目大意:同上题 多组数据 ? 由于是多组数据 因此上一题的 ?( n) 算法显然超时 ? 考虑进一步优化

? n ? ?m? ans ? ? d ? i ? ? (i ) ? Sum( ? ? , ? ? ) ? di ? ? di ? d ?1 i ?1 min( n , m ) D 2 ? n ? ?m? ? ? Sum( ? ? , ? ?)? ? i ? ? (i) ? D ? ? D ? i| D i D ?1
min( n , m ) min( n , m ) 2

D 2 ? 观察后面的 ? ? i ? ? (i ) ,如果我们能对这个函数求出一 i| D i
个前缀和,那么就可以在 ?( n ) 的时间内处理每个询问

BZOJ 2693 jzptab
? 注意到积性函数的约数和也是积性函数 ? 因此后面的那坨东西可以利用线性筛求出来 ? 线性筛当 i mod prime j ? 0 时不满足积性函数的条件,但 是由于此时 ? ( prime j ? i) ? 0,故多出来的因数的函数值都 D 是0,增加的只有原先因数的 i 部分乘了个prime[j]而已 ? 这两道题的公式都有些鬼畜,建议写这两道题之前先推推 有关公式,权当治疗公式恐惧症了


更多相关文档:

莫比乌斯环

其他重要的成就包括在 射影几何中引进齐次坐标系、莫比乌斯变换, 数论中的莫比乌斯 变换、莫比乌斯函数、莫比乌斯反演公式等等。 莫比乌斯最初学法学, 1809 年转向数学...

φ和μ通过原始定义解题

例 1:证明,若 g ( x ) = 证明如下: (莫比乌斯反演) ∑ f (k ) ,则 g ( x) = ∑ ? (k ) f ( x / k ) 。 k|x k|x n n ∑ ? (k...

信息学竞赛中的数学知识小结

3.1 扩展欧几里得 3.2 逆元 3.3 解模意义下方程 3.4 莫比乌斯反演 3.5 Miller-Rabin 素数测试 3.6 Pollard-Rho 因子分解 3.7 BSGS 离散对数 博弈论: 4.1 ...

邝斌的ACM模板。2016-7-28

[1])%MOD; ans %= MOD; } return ans; } 13、莫比乌斯反演 莫比乌斯反演公式: 14 改版人:小 Angel,初稿:2016-7-26,当前 2016-7-28,版本 1.0 { mu...

山东的大学ACM模板

0;i < fatCnt;i++) { ans *= sum(factor[i][0],B*factor[i][1])%MOD; ans %= MOD; } return ans; } tmp 13、莫比乌斯反演莫比乌斯反演公式: ...

邝斌的ACM模板

[i][1])%MOD; ans %= MOD; } return ans; } 21 / 95 改版人:小 Angel,初稿 2016-7-27,当前 2016-7-28,版本 1.0 13、莫比乌斯反演莫比乌斯反演...

山东的大学ACM模板

0;i < fatCnt;i++) { ans *= sum(factor[i][0],B*factor[i][1])%MOD; ans %= MOD; } return ans; } tmp 13、莫比乌斯反演莫比乌斯反演公式: ...

CCF青少年计算机程序设计评级标准 (简版)

3、 三维计算几何, 组合游戏中的 NIM 问题和 SG 函数, 群的概念, 置换群, Burnside 引理,Polya 原理,莫比乌斯反演定理,FFT。 能力要求 1、 具备创造性地运用...

FIU北航transfer课程介绍

(匹配、实验设计、图)等,深入浅出地表达了作者 对该领域全面和深刻的理解,介绍历史上源于数学游戏和娱乐的大量实 例以及莫比乌斯反演(作为容斥原理的推广)、格路径...

ACM模版

[pos]-=1-p; A[i][cnt]+=1; } } 组合数学 莫比乌斯反演题目大意:从点(0,0,0)出发的直线可看到多少个点(只能看到第一个,后面的视为挡住了看 不见)...
更多相关标签:
莫比乌斯反演公式 | 莫比乌斯 | 莫比乌斯函数 | 莫比乌斯环带 | 莫比乌斯环 | 莫比乌斯反演 acm | 莫比乌斯反演 popoqqq | 莫比乌斯变换 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com