PoPoQQQ 莫比烏斯反演（課堂PPT）

1、.1莫比烏斯反演吉大附中實驗學(xué)校 PoPoQQQ.2什么是莫比烏斯反演？ 介紹這個之前，我們先來看一個函數(shù) 根據(jù)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)|( )( )d nF nf d.3于是我們可以通過F(n)推導(dǎo)出f(n) f(1)=F(1) f(2)=F(2)-F(1) f(3)=F(3)-F(1) f(4)=F(4)-F(

2、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) 在推導(dǎo)的過程中我們是否發(fā)現(xiàn)了一些規(guī)律？.4莫比烏斯反演 公式： 其中 為莫比烏斯函數(shù)，定義如下： (1)若 則 (2)若 ， 為互異素數(shù)，那么 (3)其它情況下|( )( ) ( )( ) ( )d nd nnF nf df nd Fd( )d1d ( )1d12.kdp ppip( )( 1)kd ( )0d.5莫比烏斯函數(shù)的性質(zhì) (1)對于任意正整數(shù)n有： 證明： 當(dāng) 時顯然 當(dāng) 時，將 分解可以得到 在 的所有因子中， 值不為零的只有所有質(zhì)因子

3、次數(shù)都為1的因子，其中質(zhì)因數(shù)個數(shù)為 個的因子有 個 那么顯然有：|1 (1)( )0 (1)d nndn1n 1n n1212.kaaaknp ppn012|0( ).( 1)( 1)kkkiikkkkkd nidCCCCC rrkC.6莫比烏斯函數(shù)的性質(zhì) 只需證明 即可 二項式定理： 令 ，代入即可得證。0( 1)0 ()niiniCnN0()nniin inixyC x y1,1xy .7莫比烏斯函數(shù)的性質(zhì) (2)對于任意正整數(shù)n有： 其實沒什么用，結(jié)論挺好玩的可以記一下 只需要令 ，代入莫比烏斯反演的公式即可 至于為什么 就留給大家做思考題了|( )( )d ndndn( ),( )(

4、)F nn f nn|( )d nnd.8莫比烏斯函數(shù)的性質(zhì) (3)積性函數(shù) 數(shù)論上積性函數(shù)的定義： 積性函數(shù)的性質(zhì)： 積性函數(shù)的前綴和也是積性函數(shù)( )( , )1()( ) ( )( )()( ) ( )( )f nNx yf xyf x f yf nxyf xyf x f yf n設(shè)為一個定義在集合上的函數(shù)，如果對于任意有，則稱為一個積性函數(shù)；若對于任意 和 均有，則稱為一個完全積性函數(shù)(1)1f.9莫比烏斯函數(shù)的性質(zhì)由于莫比烏斯函數(shù)是積性函數(shù)，因此我們可以通過線性篩來求出莫比烏斯函數(shù)的值代碼：mu1=1;for(i=2;i=n;i+)if(!not_primei)prime+tot=i

5、;mui=-1;for(j=1;primej*i=n;j+)not_primeprimej*i=1;if(i%primej=0)muprimej*i=0;break;muprimej*i=-mui;.10BZOJ 2440 完全平方數(shù) 題目大意：求第k個無平方因子數(shù) 無平方因子數(shù)(Square-Free Number)，即分解之后所有質(zhì)因數(shù)的次數(shù)都為1的數(shù) 首先二分答案 問題轉(zhuǎn)化為求1,x之間有多少個無平方因子數(shù) 根據(jù)容斥原理可知 對于sqrt(x)以內(nèi)所有的質(zhì)數(shù) 有 x以內(nèi)的無平方因子數(shù) =0個質(zhì)數(shù)乘積的平方的倍數(shù)的數(shù)的數(shù)量(1的倍數(shù)) -每個質(zhì)數(shù)的平方的倍數(shù)的數(shù)的數(shù)量(9的倍數(shù),25的倍數(shù)

6、,.) +每2個質(zhì)數(shù)乘積的平方的倍數(shù)的數(shù)的數(shù)量(36的倍數(shù),100的倍數(shù),.)-.11BZOJ 2440 完全平方數(shù) 容易發(fā)現(xiàn)每個乘積a前面的符號恰好是 (例如 故9對答案的貢獻為負； ，故36對答案的貢獻為正) x以內(nèi)i2的倍數(shù)有 個 故有 這題和莫比烏斯反演沒關(guān)系，算是莫比烏斯函數(shù)的一個應(yīng)用吧。( )a(3)1, (6)12xi21( )( )xixQ xii.12現(xiàn)在我們來證明莫比烏斯反演定理 證明： 這里利用到了 這條性質(zhì) 形式二： 證明同理 一般要用到的都是這種形式|( )( ) ( )( ) ( )d nd nnF nf df nd Fd|( )( ) ( )( )( )( )(

7、)( )nnd nd nk nkddknf nd Fdf kf kdf nd|1 (1)( )0 (1)d nndn|( )( ) ( )( ) ( )n dn ddF nf df nF dn.13有了這個定理，我們能干什么？ 對于一些函數(shù)f(n)，如果我們很難直接求出它的值，而容易求出倍數(shù)和或約數(shù)和F(n)，那么我們可以通過莫比烏斯反演來求得f(n)的值 例：f(n)表示某一范圍內(nèi)(x,y)=n的數(shù)對的數(shù)量，F(xiàn)(n)表示某一范圍內(nèi)n|(x,y)的數(shù)對的數(shù)量 那么直接求f(n)并不是很好求，而F(n)求起來相對無腦一些，我們可以通過對F(n)進行莫比烏斯反演來求得f(n) 下面用幾道例題來為大

8、家講解一下莫比烏斯反演的好處.14BZOJ 2301 Problem b n次詢問，每次詢問有多少個數(shù)對(x,y)滿足a=x=b,c=y=d且gcd(x,y)=k N=5W,1=a=b=5W,1=c=d=5W 首先利用容斥原理將一個詢問拆分成四個，每次詢問有多少個數(shù)對(x,y)滿足1=x=n,1=y=m且gcd(x,y)=k 這個問題等價于詢問有多少個數(shù)對(x,y)滿足1=x=floor(n/k),1=y=floor(m/k)且x與y互質(zhì) 利用NOI2010能量采集中的方法，我們可以得到一個O(nlogn)的算法，但是這顯然不能勝任此題的數(shù)據(jù)范圍 這時候我們就可以考慮莫比烏斯反演了.15BZO

9、J 2301 Problem b 由于之前的結(jié)論，我們可以令f(i)為1=x=n,1=y=m且gcd(x,y)=i的數(shù)對(x,y)的個數(shù)，F(xiàn)(i)為1=x=n,1=ym) swap(n,m); for(i=1;i=n;i=last+1) last=min(n/(n/i),m/(m/i);re+=(n/i)*(m/i)*(sumlast-sumi-1); return re; 超級好寫不是么？.18BZOJ 2820 YGY的GCD 題目大意：求有多少數(shù)對(x,y)(1=x=n,1=y=m)滿足gcd(x,y)為質(zhì)數(shù) n,m=1000W 數(shù)據(jù)組數(shù)=1W 首先我們枚舉每一個質(zhì)數(shù) 那么答案就是 直接

10、做顯然TLE 考慮優(yōu)化 令 ，那么有min( ,) min( ,)1( )n mn mpdnmansdpdpdpdTmin( ,)1|()n mTpTnmTansTTp.19BZOJ 2820 YGY的GCD 如果能求出 的前綴和，這個問題就能在 時間內(nèi)出解。 只需要暴力枚舉每一個質(zhì)數(shù)，去更新這個質(zhì)數(shù)的倍數(shù)即可。 由 這個結(jié)論易知每個質(zhì)數(shù)更新時是均攤 的，而質(zhì)數(shù)個數(shù)恰好為 故暴力枚舉+維護前綴和的時間復(fù)雜度即為 。|()pTTp()n11limlnnninri(log )n( /log )nn( )n.20BZOJ 3529 數(shù)表 題目大意：令F(i)為i的約數(shù)和，q次給定n,m,a,求 n,

11、m=105,q=2W,a=109 a的限制十分討厭 我們首先假設(shè)沒有這個限制 令g(i)為1=x=n,1=y=m,gcd(x,y)=i的數(shù)對(x,y)的個數(shù) 那么顯然有31 1 1(gcd( , )(gcd( , ) mod 2injmFi jaFi j |( )( )i ddnmg iidd.21BZOJ 3529 數(shù)表 F(i)利用線性篩可以在O(n)時間內(nèi)處理出來 那么就有 治好了我多年的公式恐懼癥 現(xiàn)在我們只要有 的前綴和就可以在 時間內(nèi)解決這個弱化版的問題 與上一題相同，枚舉每一個i，暴力更新i的倍數(shù)，然后處理前綴和，這樣做是O(nlogn)的 那么現(xiàn)在有了a的限制怎么搞呢？min(

12、 ,)min( ,)min( ,)11|1|( ) ( )( )( )( ) ( )n mn mn miii ddi ddnmnmdansF i g iF iF iiddddi|( ) ( )i ddF ii()n.22BZOJ 3529 數(shù)表 我們發(fā)現(xiàn)對答案有貢獻的i只有F(i)=a的i 我們離線處理，將詢問按照a排序，i按照F(i)排序 每次詢問將所有F(i)=a的i按照之前的方式插入 用樹狀數(shù)組維護前綴和即可 時間復(fù)雜度 取?？梢岳米匀灰绯鰅nt 最后再對231-1取與即可2( loglog )nnq nn.23BZOJ 2154 Crash的數(shù)字表格 題目大意：給定n,m,求 (n,

13、m=107) 枚舉 令 則有11( , )nmijlcm i j1111( , )gcd( , )nmnmijiji janslcm i ji jgcd( , )di j 1 1gcd( , ) 1( , )ixjyi jF x yi j 2min( ,)min( ,)11(,)(,)n mn mddnmdFnmddansd Fddd .24BZOJ 2154 Crash的數(shù)字表格 繼續(xù)令 那么根據(jù)莫比烏斯反演可以推出 不是很好推，和之前的思路一樣，我不當(dāng)堂推了 將兩個式子分別進行 的計算 可以得到一個 的算法 至此本題已經(jīng)可以解決。11(1)(1)( , )22yxijx xy ySum x yi jmin( , )21( , )( )(,)x yixyF x yiiSumii ()n()( )nnn .25BZOJ 2693 jzptab 題目大意：同上題 多組數(shù)據(jù) 由于是多組數(shù)據(jù) 因此上一題的 算法顯然超時 考慮進一步優(yōu)化 觀察后面的 ，如果我們能對這個函數(shù)求出一 個前綴和，那么就可以在 的時間內(nèi)處理每個詢問( )nmin( ,)min( ,)211min( ,)21|( )(,) (,)( )n mn mdin mDi DnmansdiiSumdidin