莫比烏斯變換

2023/1/31莫比烏斯變換上海大學(xué)沈云付yfshen@上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院1、引言莫比烏斯變換1）復(fù)平面上的莫比烏斯變換公元1858年，德國(guó)數(shù)學(xué)家莫比烏斯(Mobius，1790～1868)發(fā)現(xiàn)：把一個(gè)扭轉(zhuǎn)180°后再兩頭粘接起來(lái)的紙條，具有魔術(shù)般的性質(zhì)。這樣的紙帶只有一個(gè)面(即單側(cè)曲面)，一只小蟲(chóng)可以爬遍整個(gè)曲面而不必跨過(guò)它的邊緣！這種由莫比烏斯發(fā)現(xiàn)的神奇的單面紙帶，稱為“莫比烏斯帶”。幾何學(xué)中的莫比烏斯變換：其中z,a,b,c,d為復(fù)數(shù)且滿足ad?bc0.2023/1/311、引言莫比烏斯變換2）數(shù)論中的莫比烏斯變換對(duì)于給定的數(shù)論函數(shù)f(n)，（nN），定義新的數(shù)論函數(shù)稱F(n)為f(n)的莫比烏斯變換，而f(n)為F(n)的莫比烏斯逆變換。2023/1/312、數(shù)論莫比烏斯變換計(jì)算實(shí)例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)2023/1/31莫比烏斯逆變換計(jì)算實(shí)例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)2023/1/313、逆變換與莫比烏斯函數(shù)觀察發(fā)現(xiàn)f(n)的表示式中有形式為F(n/d)的項(xiàng)。引入莫比烏斯函數(shù)(n)，記(d)為F(n/d)的符號(hào)+或-之一有(1)=(6)=1,(2)=(3)=(5)=(7)=-1，(4)=(8)=0。若p是素?cái)?shù)，由F(p)=f(1)+f(p)，得f(p)=F(p)-F(1)，因此(p)=-1。繼續(xù)觀察，F(xiàn)(p2)=f(1)+f(p)+f(p2)，得f(p2)=F(p2)-(F(p)-F(1))-F(1)=F(p2)-F(p)，這又有(p2)=0。同理推出，f(p3)=F(p3)-F(p2)，這又有(p3)=0，繼續(xù)推下去，有當(dāng)k>1，有(pk)=0。2023/1/31莫比烏斯函數(shù)(n)繼續(xù)觀察：設(shè)p1，p2為不同素?cái)?shù)F(p1*p2)=f(p1*p2)+f(p1)+f(p2)+f(1)，得f(p1*p2)=F(p1*p2)-F(p1)-F(p2)+F(1)。這里有(1)=1,(p2)=-1,(p1)=-1,(p1*p2)=1。2023/1/31莫比烏斯函數(shù)(n)總結(jié)得2023/1/31積性函數(shù)積性函數(shù)f(n)：對(duì)數(shù)論函數(shù)f(n)，如果滿足對(duì)任意正整數(shù)m，n，只要gcd(m,n)=1，就有f(mn)=f(m)f(n)，那么稱f(n)為積性函數(shù)完全積性函數(shù)g(n)：對(duì)數(shù)論函數(shù)g(n)，如果滿足對(duì)任意正整數(shù)m，n，均有g(shù)(mn)=g(m)g(n)，那么稱g(n)完全積性函數(shù)2023/1/31莫比烏斯函數(shù)的性質(zhì)莫比烏斯函數(shù)是積性函數(shù)，即若gcd(m,n)=1，則(mn)=(m)(n)；若gcd(m,n)>1，則(mn)=0；對(duì)于f(n)=1的特例，證明：首先(n)是積性函數(shù)，因此用下面將證明的一個(gè)命題可知I(n)也是積性函數(shù)。顯然，I(1)=1;

而對(duì)素?cái)?shù)p，I(pt)=1+(p)+(p2)+…+(pt)=1-1+0+…+0=0.證畢2023/1/31計(jì)算莫比烏斯函數(shù)的程序?qū)崿F(xiàn)voidMobius(){//計(jì)算d的不同素因子個(gè)數(shù)，計(jì)算(d)的值memset(vis,0,sizeof(vis));//vis[i]記錄記錄i是否標(biāo)記過(guò)mu[1]=1;cnt=0;for(inti=2;i<N;i++){if(!vis[i]){//如果vis[i]是第1個(gè)未標(biāo)記的，那么i是素?cái)?shù)prime[cnt++]=i;mu[i]=-1;}for(intj=0;j<cnt&&i*prime[j]<N;j++){//用篩法求素?cái)?shù)vis[i*prime[j]]=1;//將prime[j]的倍數(shù)都標(biāo)記，即篩掉if(i%prime[j])mu[i*prime[j]]=-mu[i];//若i未被篩掉，則用積性求else{mu[i*prime[j]]=0;break;//被篩掉的數(shù)都有素?cái)?shù)的平方，=0}}}}2023/1/314、莫比烏斯函數(shù)性質(zhì)-定理1定理1：設(shè)f(n)和F(n)均為定義在N上的數(shù)論函數(shù)，f(n)不恒為0，若f(n)為積性函數(shù)，則F(n)也為積性函數(shù)。證：設(shè)n有標(biāo)準(zhǔn)分解已知F(1)=f(1)=1。n的任一正因子d，可寫(xiě)為因此2023/1/31因此，F(xiàn)(n)為積性函數(shù)4、莫比烏斯函數(shù)性質(zhì)-定理2定理2：設(shè)f(n)和F(n)均為定義在N上的數(shù)論函數(shù)，那么F(n)為f(n)的莫比烏斯變換，即的充要條件是這里，為莫比烏斯函數(shù)，2023/1/31注：因d遍歷n的所有因子，當(dāng)且僅當(dāng)，n/d遍歷n的所有因子。因此f(n)也可寫(xiě)預(yù)備對(duì)于k|(n/d)，指有整數(shù)q使得n/d=kq，即n=dkq即d|(n/k)，d|n2023/1/31證明必要性：設(shè)成立，那么2023/1/31證明充分性：設(shè)成立，那么令d=km，那么2023/1/313個(gè)特例之1、2設(shè)f1(n)=n，那么為n的所有正因子之和。如設(shè)，那么F1(n)=根據(jù)反演公式有設(shè)f2(n)=1，那么為n的所有正因子個(gè)數(shù)(1+1)(2+1)…

(k+1)。有類似反演公式，很神奇。2023/1/312023/1/313個(gè)特例之3若f(n)是歐拉函數(shù)(n)，則反演后莫比烏斯變換的另一種有用形式設(shè)f(n)，F(xiàn)(n)為整數(shù)函數(shù)，1n,dN。記那么有證明：以下假定：n,dN記有證明歸類合并證明這里利用了5、莫比烏斯函數(shù)應(yīng)用-Eratosthenes篩法設(shè)A=<a1,a2,…,an>為整數(shù)序列（可重復(fù)），記d為正整數(shù)，Ad=<a：d|a，a是a1,a2,…an其中之一>，用|Ad|記序列Ad中元素的個(gè)數(shù)。

舉例：

如A=<6,8,15,7,17,21,6,11,23,21>，d=3，那么A3=<6,15,21,6,21>，元素個(gè)數(shù)為5.A7=<7,21,21>，元素個(gè)數(shù)為3.2023/1/31定理3、Eratosthenes篩法定理3、設(shè)m為正整數(shù)，p1,p2,…pt為m的所有不同的素因子。那么序列A中與m既約的整數(shù)的個(gè)數(shù)為證明：已有結(jié)論特別地，因此2023/1/31舉例-求不超過(guò)120的素?cái)?shù)的個(gè)數(shù)

解：不超過(guò)120的合數(shù)必是2、3、5或7的真倍數(shù)。記m=2*3*5*7=210，記A=[1..120]，d|210，記Ad={a：d|a，0<a<121}，|Ad|=120/d2023/1/31d1235761014152135304270105210(d)1-1-1-1-1111111-1-1-1-11|Ad|1206040241720128853421101到120中與120既約的整數(shù)的個(gè)數(shù)為=120-60-40-24-17+(20+12+8+8+5+3)-4-2-1-1=120-141+56-8=27，而2、3、5、7雖與120不既約，但是素?cái)?shù)。1不是素?cái)?shù)。因此不超過(guò)120的素?cái)?shù)的個(gè)數(shù)=27+4-1=30容斥原理與莫比烏斯變換對(duì)照兩個(gè)集合的容斥關(guān)系公式：A∪B=|A∪B|=|A|+|B|-|A∩B|(∩：重合的部分）三個(gè)集合的容斥關(guān)系公式：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|一般地，設(shè)S為有限集，AiS，則2023/1/31思考在1到1000的自然數(shù)中，能被3或5整除的數(shù)共有多少個(gè)？不能被3或5整除的數(shù)共有多少個(gè)？解：略分母是1001的最簡(jiǎn)分?jǐn)?shù)一共有多少個(gè)？分析：這一題實(shí)際上就是找分子中不能與1001進(jìn)行約分的數(shù)。由于1001=7×11×13，所以就是找不能被7，11，13整除的數(shù)。由容斥原理知：在1~1001中，能被7或11或13整除的數(shù)有（143+91+77）-（13+11+7）+1=281（個(gè)），從而不能被7、11或13整除的數(shù)有1001-281=720（個(gè)）.也就是說(shuō)，分母為1001的最簡(jiǎn)分?jǐn)?shù)有720個(gè)。2023/1/31定理3推論推論：設(shè)m為正整數(shù)，那么序列A中使gcd(m,a)=k的整數(shù)的個(gè)數(shù)為2023/1/31序列A的幾種常見(jiàn)形式設(shè)A為整數(shù)的一個(gè)序列，m為正整數(shù)。那么設(shè)n為正整數(shù)，A為1到n的自然數(shù)的序列。那么Ad=<a：若d|a且an>，|Ad|=[n/d]那么1到n中與m互質(zhì)的自然數(shù)的個(gè)數(shù)為特別地，1到n中與n互質(zhì)的自然數(shù)的個(gè)數(shù)為2023/1/31可用于求1到n中素?cái)?shù)個(gè)數(shù)序列A的幾種常見(jiàn)形式設(shè)n為正整數(shù)，A為1到n的所有自然數(shù)對(duì)(a,b)的gcd序列，即A=<gcd(a,b)：若an,bn>，A共有n2個(gè)元素，Ad=<gcd(a,b)：若d|gcd(a,b),且an,bn>，顯然|Ad|=[n/d][n/d]A中與m互質(zhì)的自然數(shù)的個(gè)數(shù)為設(shè)A為1到n的所有自然數(shù)對(duì)(a,b,c)的gcd序列，那么|Ad|=[n/d][n/d][n/d]。A中與m互質(zhì)的自然數(shù)的個(gè)數(shù)為2023/1/31注意：有許多重復(fù)的例1、公因數(shù)為質(zhì)數(shù)問(wèn)題/JudgeOnline/problem.php?id=2818問(wèn)題描述：給一個(gè)正整數(shù)n，其中n<=107，求使得gcd(x,y)為質(zhì)數(shù)的(x,y)的個(gè)數(shù)，（1<=x,y<=n）。分析：要使得一個(gè)數(shù)gcd(x,y)為質(zhì)數(shù)，可枚舉小于等于n的質(zhì)數(shù)p，那么對(duì)于每一個(gè)質(zhì)數(shù)，只需要考慮在區(qū)間[1,n/p]中，滿足序?qū)?x,y)互質(zhì)的對(duì)數(shù)。不妨設(shè)xy，那么如果枚舉每一個(gè)y，小于y有多少個(gè)x與y互素，這正是歐拉函數(shù)，即(y)。所以可用遞推法求歐拉函數(shù)，將得到的答案乘以2即可。但還有漏計(jì)算的，即x=y且y為素?cái)?shù)的情況，再加上就行了。參考代碼見(jiàn)下頁(yè)。2023/1/31#include<iostream>#include<bitset>usingnamespacestd;typedeflonglongLL;constintN=10000010;bitset<N>prime;LLphi[N],f[N];intp[N],k;voidisprime(){//求素?cái)?shù)組k=0;prime.set();for(inti=2;i<N;i++){if(prime[i]){p[k++]=i;for(intj=i+i;j<N;j+=i)2023/1/31prime[j]=false;}}}voidInit(){//求(i)inti,j;for(i=1;i<N;i++)phi[i]=i;for(i=2;i<N;i+=2)phi[i]>>=1;for(i=3;i<N;i+=2){if(phi[i]==i){for(j=i;j<N;j+=i)phi[j]=phi[j]-phi[j]/i;}}f[1]=0;for(i=2;i<N;i++)f[i]=f[i-1]+(phi[i]<<1);}LLSolve(intn){LLans=0;for(inti=0;i<k&&p[i]<=n;i++)ans+=1+f[n/p[i]];returnans;}intmain(){Init();isprime();intn;scanf("%d",&n);printf("%I64d\n",Solve(n));return0;}2023/1/31例2、公因數(shù)為質(zhì)數(shù)問(wèn)題-進(jìn)一步/acdreamers/article/details/8542292#comments問(wèn)題描述：給定正整數(shù)m,n，其中n<=107，求使得gcd(x,y)為質(zhì)數(shù)的(x,y)的個(gè)數(shù)，1<=x<=m，1<=y<=n。分析：用莫比烏斯反演來(lái)解決。2023/1/31例解：記A=<{gcd(x,y):1xn，1ym}>；f(d)=|<{gcd(x,y):gcd(x,y)=d，1xn，1ym}>|，即A中使得gcd(x,y)=d的數(shù)的個(gè)數(shù)。再記即F(k)是滿足k|gcd(x,y)的數(shù)對(duì)(x,y)的個(gè)數(shù)。那么，顯然根據(jù)反演公式題目要求gcd(x,y)為質(zhì)數(shù)，那么我們枚舉每一個(gè)質(zhì)數(shù)q，然后得到本題需要優(yōu)化用Eratosthenes篩法的嘗試設(shè)A為a在[1,m]，b在[1,n]的所有自然數(shù)對(duì)(x,y)的gcd序列，即A=<gcd(x,y)：若1xm,1yn>，A共有mn個(gè)元素，Ad=<gcd(x,y)：若d|gcd(x,y),且xn,yn>，顯然|Ad|=[m/d][n/d]2023/1/31分析對(duì)于正整數(shù)q，序列A中與q互質(zhì)的整數(shù)a的個(gè)數(shù)為題目要求gcd(x,y)是質(zhì)數(shù)，現(xiàn)枚舉每一個(gè)質(zhì)數(shù)q。對(duì)于固定的質(zhì)數(shù)q，序列A中使與q不互質(zhì)的整數(shù)a就是使得gcd(x,y)=q的數(shù)，個(gè)數(shù)為mn-Sq。因此，序列A中為質(zhì)數(shù)的整數(shù)a個(gè)數(shù)為2023/1/31例3、MophuesSource：/showproblem.php?pid=4746Description:任何整數(shù)C(C>=2)都可以寫(xiě)成素?cái)?shù)之積

C=p1×p2×p3×...×pk

其中，p1,p2...pk

是素?cái)?shù)。如C=24,則24=2×2×2×3,其中,p1=p2=p3=2,p4=3,k=4.

給定兩整數(shù)P和C,若k<=P(k是C的素因子個(gè)數(shù)),稱C是P的幸運(yùn)數(shù).

現(xiàn)小X需計(jì)算的點(diǎn)對(duì)(a,b)的個(gè)數(shù),其中1<=a<=n,1<=b<=m,gcd(a,b)是P的幸運(yùn)數(shù)(“gcd”是最大公因數(shù)).

注意：因?yàn)?無(wú)素因子，定義1為任何非負(fù)數(shù)的幸運(yùn)數(shù).2023/1/31Input

首行有一個(gè)整數(shù)T，表示有T組測(cè)試數(shù)據(jù).接下來(lái)有T行，每行是一種測(cè)試數(shù)據(jù)，含3個(gè)非負(fù)整數(shù)n,m與P(n,m,P<=5×105.T<=5000).Output

對(duì)每種測(cè)試數(shù)據(jù)，輸出對(duì)(a,b)的個(gè)數(shù)，其中1<=a<=n,1<=b<=m,且gcd(a,b)是P的幸運(yùn)數(shù).2023/1/31SampleInput21010010101SampleOutput6393Mophues分析題意：給出n,m,p，求(a,b)的對(duì)數(shù)：滿足gcd(a,b)的素因子個(gè)數(shù)<=p，(其中1<=a<=n,1<=b<=m)分析：設(shè)f(d)：gcd(a,b)=d的(a,b)的組數(shù)，F(xiàn)(k):k|gcd(a,b)的(a,b)的組數(shù)，易知F(k)=[n/k]*[m/k]；對(duì)整數(shù)k，枚舉k的素因子個(gè)數(shù)使得總數(shù)<=p，這種k記作k(p)k(p)=k，當(dāng)k的素因子個(gè)數(shù)不超過(guò)pk(p)=0，當(dāng)k的素因子個(gè)數(shù)超過(guò)p。程序?qū)崿F(xiàn)：見(jiàn)下頁(yè)include<cstdio>#include<cstdlib>#include<iostream>usingnamespacestd;constintM=555555,intN=19;intg[M][N],num[M];intpri[M],pnum,mu[M],vis[M];intcalc(inty,intx){//統(tǒng)計(jì)y中因子x出現(xiàn)的次數(shù)

intret=0; while(y%x==0){ ret++; y/=x; } returnret;}2023/1/31intmain(){ intT,n,m,P,i,j;init();cin>>T; while(T--){ cin>>n>>m>>P; longlongans=0; if(P>=N){ cout<<(longlong)n*m<<endl; continue; } if(n>m)swap(n,m); for(i=1;i<=n;i=j+1){ j=min(n/(n/i),m/(m/i)); ans+=((longlong)g[j][P] -g[i-1][P])*(n/i)*(m/i); } cout<<ans<<endl;} return0;}voidinit(){//計(jì)算(d)的值 intn=M-1;memset(num,0,sizeof(num)); memset(g,0,sizeof(f)); memset(mu,0,sizeof(mu)); memset(vis,0,sizeof(vis)); pnum=0;vis[1]=mu[1]=1;for(inti=2;i<=n;i++){ if(!vis[i]){pri[pnum++]=i;mu[i]=-1;} for(intj=0;j<pnum;j++){ if(i*pri[j]>n)break; vis[i*pri[j]]=1; if(i%pri[j]==0){mu[i*pri[j]]=0;break;} mu[i*pri[j]]=-mu[i]; }}2023/1/31 for(inti=2;i<=n;i++) if(num[i]==0) for(intj=i;j<=n;j+=i)num[j]+=calc(j,i); for(inti=1;i<=n;i++) for(intj=i;j<=n;j+=i) g[j][num[i]]+=mu[j/i]; for(inti=1;i<=n;i++) for(intj=1;j<N;j++) g[i][j]+=g[i][j-1]; for(inti=1;i<=n;i++) for(intj=0;j<N;j++) g[i][j]+=g[i-1][j];}注：num[j]記錄j的因子數(shù)。g[j][num[i]]用于計(jì)算具有相同個(gè)數(shù)的素因子的i的(j/i)之和，2023/1/31例4、可見(jiàn)格點(diǎn)Soucee：SPOJ7001Description有N*N*N網(wǎng)格.一個(gè)角落在(0,0,0)，對(duì)頂角落是(N,N,N).問(wèn)從(0,0,0)看有多少個(gè)格點(diǎn)是可見(jiàn)的？點(diǎn)X從點(diǎn)Y可見(jiàn)，當(dāng)且僅當(dāng)，線段XY上沒(méi)有其他的點(diǎn)。Input:第一行是測(cè)試數(shù)據(jù)個(gè)數(shù)T。接著有T行每行有一個(gè)整數(shù)N.Output:輸出T行，每行是對(duì)應(yīng)的可見(jiàn)格點(diǎn)的個(gè)數(shù)。2023/1/31SampleInput:3125

SampleOutput:719175

Constraints:T<=501<=N<=10000002023/1/31可見(jiàn)格點(diǎn)-分析本題要求使gcd(a,b,c)=1且

a,b,c<=N的(a,b,c)的數(shù)對(duì)總數(shù)。用莫比烏斯反演可以求解。設(shè)f(n)為gcd(a,b,c)=n的數(shù)對(duì)(a,b,c)組數(shù),記即F(k)為

k|gcd(a,b,c)的(a,b,c)組數(shù)。那么F(k)=(N/k)*(N/k)*(N/k)。(取整)2023/1/312023/1/31可見(jiàn)格點(diǎn)-分析經(jīng)反演后，得特別地，再考慮總和：三個(gè)坐標(biāo)軸，共3個(gè)

空間中N