莫比烏斯反演什么是莫比烏斯反演？介紹這個(gè)之前，我們先來(lái)看一個(gè)函數(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)于是我們可以通過(guò)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)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)的過(guò)程中我們是否發(fā)現(xiàn)了一些規(guī)律？莫比烏斯函數(shù)的性質(zhì)(1)對(duì)于任意正整數(shù)n有：證明：①當(dāng)時(shí)顯然②當(dāng)時(shí)，將分解可以得到在的所有因子中，值不為零的只有所有質(zhì)因子次數(shù)都為1的因子，其中質(zhì)因數(shù)個(gè)數(shù)為個(gè)的因子有個(gè)那么顯然有：莫比烏斯函數(shù)的性質(zhì)只需證明即可二項(xiàng)式定理：令，代入即可得證。莫比烏斯函數(shù)的性質(zhì)(2)對(duì)于任意正整數(shù)n有：其實(shí)沒(méi)什么用，結(jié)論挺好玩的可以記一下只需要令，代入莫比烏斯反演的公式即可至于為什么就留給大家做思考題了莫比烏斯函數(shù)的性質(zhì)(3)積性函數(shù)數(shù)論上積性函數(shù)的定義：積性函數(shù)的性質(zhì)：①②積性函數(shù)的前綴和也是積性函數(shù)BZOJ2440完全平方數(shù)題目大意：求第k個(gè)無(wú)平方因子數(shù)無(wú)平方因子數(shù)(Square-FreeNumber)，即分解之后所有質(zhì)因數(shù)的次數(shù)都為1的數(shù)首先二分答案問(wèn)題轉(zhuǎn)化為求[1,x]之間有多少個(gè)無(wú)平方因子數(shù)根據(jù)容斥原理可知對(duì)于sqrt(x)以內(nèi)所有的質(zhì)數(shù)有x以內(nèi)的無(wú)平方因子數(shù)=0個(gè)質(zhì)數(shù)乘積的平方的倍數(shù)的數(shù)的數(shù)量(1的倍數(shù))-每個(gè)質(zhì)數(shù)的平方的倍數(shù)的數(shù)的數(shù)量(9的倍數(shù),25的倍數(shù),...)+每2個(gè)質(zhì)數(shù)乘積的平方的倍數(shù)的數(shù)的數(shù)量(36的倍數(shù),100的倍數(shù),...)-...現(xiàn)在我們來(lái)證明莫比烏斯反演定理證明：這里利用到了這條性質(zhì)形式二：證明同理一般要用到的都是這種形式BZOJ2301Problembn次詢問(wèn)，每次詢問(wèn)有多少個(gè)數(shù)對(duì)(x,y)滿足a<=x<=b,c<=y<=d且gcd(x,y)=kN<=5W,1<=a<=b<=5W,1<=c<=d<=5W首先利用容斥原理將一個(gè)詢問(wèn)拆分成四個(gè)，每次詢問(wèn)有多少個(gè)數(shù)對(duì)(x,y)滿足1<=x<=n,1<=y<=m且gcd(x,y)=k這個(gè)問(wèn)題等價(jià)于詢問(wèn)有多少個(gè)數(shù)對(duì)(x,y)滿足1<=x<=floor(n/k),1<=y<=floor(m/k)且x與y互質(zhì)利用NOI2010能量采集中的方法，我們可以得到一個(gè)O(nlogn)的算法，但是這顯然不能勝任此題的數(shù)據(jù)范圍這時(shí)候我們就可以考慮莫比烏斯反演了BZOJ2301Problemb由于之前的結(jié)論，我們可以令f(i)為1<=x<=n,1<=y<=m且gcd(x,y)=i的數(shù)對(duì)(x,y)的個(gè)數(shù)，F(xiàn)(i)為1<=x<=n,1<=y<=m且i|gcd(x,y)的數(shù)對(duì)(x,y)的個(gè)數(shù)那么顯然有反演后可得枚舉原題中k的每一個(gè)倍數(shù)，我們就可以O(shè)(n)時(shí)間處理每個(gè)詢問(wèn)了但是O(n)還是不能勝任本題的數(shù)據(jù)范圍考慮進(jìn)一步優(yōu)化BZOJ2301Problemb觀察式子，發(fā)現(xiàn)最多有個(gè)取值那么就至多有個(gè)取值枚舉這個(gè)取值，對(duì)莫比烏斯函數(shù)維護(hù)一個(gè)前綴和，就可以在時(shí)間內(nèi)出解總時(shí)間復(fù)雜度枚舉除法的取值這種方法在莫比烏斯反演的應(yīng)用當(dāng)中非常常用，且代碼并不難寫(xiě)不難寫(xiě)？怎么寫(xiě)？BZOJ2301Problembif(n>m)s);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]);}returnre;超級(jí)好寫(xiě)不是么？BZOJ2820YGY的GCD題目大意：求有多少數(shù)對(duì)(x,y)(1<=x<=n,1<=y<=m)滿足gcd(x,y)為質(zhì)數(shù)n,m<=1000W數(shù)據(jù)組數(shù)<=1W首先我們枚舉每一個(gè)質(zhì)數(shù)那么答案就是直接做顯然TLE考慮優(yōu)化令，那么有BZOJ3529數(shù)表題目大意：令F(i)為i的約數(shù)和，q次給定n,m,a,求n,m<=10^5,q<=2W,a<=10^9a的限制十分討厭我們首先假設(shè)沒(méi)有這個(gè)限制令g(i)為1<=x<=n,1<=y<=m,gcd(x,y)=i的數(shù)對(duì)(x,y)的個(gè)數(shù)那么顯然有BZOJ3529數(shù)表F(i)利用線性篩可以在O(n)時(shí)間內(nèi)處理出來(lái)那么就有治好了我多年的公式恐懼癥~~現(xiàn)在我們只要有的前綴和就可以在時(shí)間內(nèi)解決這個(gè)弱化版的問(wèn)題與上一題相同，枚舉每一個(gè)i，暴力更新i的倍數(shù)，然后處理前綴和，這樣做是O(nlogn)的那么現(xiàn)在有了a的限制怎么搞呢？BZOJ2154Crash的數(shù)字表格題目大意：給定n,m,求(n,m<=10^7)枚舉令則有BZOJ2154Crash的數(shù)字表格繼續(xù)令那么根據(jù)莫比烏斯反演可以推出不是很好推，和之前的思路一樣，我不當(dāng)堂推了將兩個(gè)式子分別進(jìn)行的計(jì)算可以得到一個(gè)的算法至此本題已經(jīng)可以解決。BZOJ2693jzptab注意到積性函數(shù)的約數(shù)和也是積性函數(shù)因此后面的那坨東西可以利用線性篩求出來(lái)線性篩當(dāng)