莫比烏斯變換

1、2022-2-24莫比烏斯變換莫比烏斯變換上海大學上海大學 沈云付沈云付上海大學計算機工程與科學學院上海大學計算機工程與科學學院1、引言、引言 莫比烏斯變換莫比烏斯變換 1）復平面上的莫比烏斯變換）復平面上的莫比烏斯變換 公元公元18581858年，德國數(shù)學家莫比烏斯年，德國數(shù)學家莫比烏斯(Mobius(Mobius，179017901868)1868)發(fā)現(xiàn)：把一個扭轉發(fā)現(xiàn)：把一個扭轉180180后再兩頭粘后再兩頭粘接起來的紙條，具有魔術般的性質。這樣的紙帶只接起來的紙條，具有魔術般的性質。這樣的紙帶只有一個面有一個面( (即單側曲面即單側曲面) )，一只小蟲可以爬遍整個曲，一只小蟲可以爬遍整

2、個曲面而不必跨過它的邊緣！這種由莫比烏斯發(fā)現(xiàn)的神面而不必跨過它的邊緣！這種由莫比烏斯發(fā)現(xiàn)的神奇的單面紙帶，稱為奇的單面紙帶，稱為“莫比烏斯帶莫比烏斯帶”。 幾何學中的莫比烏斯變換：幾何學中的莫比烏斯變換： 其中其中 z, a, b, c, d z, a, b, c, d 為為 復數(shù)復數(shù) 且滿足且滿足 adadbcbc 0.0.2022-2-24dczbazzf)(1、引言、引言 莫比烏斯變換莫比烏斯變換 2）數(shù)論中的莫比烏斯變換）數(shù)論中的莫比烏斯變換 對于給定的數(shù)論函數(shù)對于給定的數(shù)論函數(shù)f(n)，（，（n N），定義新的數(shù)），定義新的數(shù)論函數(shù)論函數(shù) 稱稱F(n)為為f(n)的莫比烏斯變換，而的

3、莫比烏斯變換，而f(n)為為F(n)的莫的莫比烏斯逆變換。比烏斯逆變換。2022-2-24nddfnF|)()(2、數(shù)論莫比烏斯變換計算實例、數(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)2022-2-24莫比烏斯逆變換計算實例莫比烏斯逆變換計算實例 f(1)=F(1) f(2)=F(2)-F(1) f(3)=F(3)-F(1) f(4)=

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)2022-2-243、逆變換與莫比烏斯函數(shù)、逆變換與莫比烏斯函數(shù) 觀察發(fā)現(xiàn)觀察發(fā)現(xiàn)f(n)的表示式中有形式為的表示式中有形式為 F(n/d)的項。的項。 引入莫比烏斯函數(shù)引入莫比烏斯函數(shù) (n)，記，記 (d)為為 F(n/d)的符號的符號+或或-之一之一 有有 (1)= (6)=1, (2)= (3)= (5)= (7)=-1， (4)= (8)=0。 若若p是素數(shù)，由是素數(shù)，由F(p)=f(1)+f(p)，得，得f(p)=F(p)-F

5、(1)，因此，因此 (p)=-1。 繼續(xù)觀察，繼續(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ù)推下去，繼續(xù)推下去，有當，有當k1，有，有 (pk)=0。2022-2-24nddnFdnf|)()()(莫比烏斯函數(shù)莫比烏斯函數(shù) (n) 繼續(xù)觀察：繼續(xù)觀察： 設設p1，p2為不同素數(shù)為不同素數(shù) F(p1*p2)=f(p1*p2)+f(p1)+f(p2)+f(1)，得，得f(p1*p2)

6、=F(p1*p2)-F(p1)-F(p2)+F(1)。 這里有這里有 (1)=1, (p2)=-1, (p1)=-1, (p1*p2)=1。2022-2-24莫比烏斯函數(shù)莫比烏斯函數(shù) (n) 總結得總結得2022-2-24其它為不同素數(shù)、，rrrppppppnnd.10) 1(1)(2121積性函數(shù)積性函數(shù) 積性函數(shù)積性函數(shù)f(n) ：對數(shù)論函數(shù)：對數(shù)論函數(shù)f(n)，如果滿足對任意，如果滿足對任意正整數(shù)正整數(shù)m，n，只要，只要gcd(m,n)=1，就有，就有f(mn)=f(m)f(n)，那么稱，那么稱f(n)為積性函數(shù)為積性函數(shù) 完全積性函數(shù)完全積性函數(shù)g(n) ：對數(shù)論函數(shù)：對數(shù)論函數(shù)g(n

7、)，如果滿足，如果滿足對任意正整數(shù)對任意正整數(shù)m，n，均有，均有g(mn)=g(m)g(n)，那么，那么稱稱g(n)完全積性函數(shù)完全積性函數(shù)2022-2-24莫比烏斯函數(shù)的性質莫比烏斯函數(shù)的性質 莫比烏斯函數(shù)是積性函數(shù)，即莫比烏斯函數(shù)是積性函數(shù)，即1. 若若gcd(m,n)=1，則，則 (mn)= (m) (n)；2. 若若gcd(m,n)1，則，則 (mn)=0；3. 對于對于f(n)=1的特例，的特例，證明：首先證明：首先 (n)是積性函數(shù)，因此用下面將證明的一是積性函數(shù)，因此用下面將證明的一個命題可個命題可 知知I(n)也是積性函數(shù)。顯然，也是積性函數(shù)。顯然，I(1)=1; 而對素數(shù)而對

8、素數(shù)p，I(pt)=1+ (p)+ (p2)+ (pt) =1-1+0+0=0. 證畢證畢2022-2-2410111)()(|nnndnInd計算莫比烏斯函數(shù)的程序實現(xiàn)計算莫比烏斯函數(shù)的程序實現(xiàn)void Mobius() /計算計算d的不同素因子個數(shù)，計算的不同素因子個數(shù)，計算 (d)的值的值 memset(vis,0,sizeof(vis); /visi記錄記錄記錄記錄i是否標記過是否標記過 mu1 = 1; cnt = 0; for(int i=2; iN; i+) if(!visi) /如果如果visi是第是第1個未標記的，那么個未標記的，那么i是素數(shù)是素數(shù) primecnt+ = i

9、; mui = -1; for(int j=0; jcnt&i*primejN; j+) /用篩法求素數(shù)用篩法求素數(shù) visi*primej = 1; /將將primej的倍數(shù)都標記，即篩掉的倍數(shù)都標記，即篩掉 if(i%primej) mui*primej = -mui; /若若i未被篩掉，則用積性求未被篩掉，則用積性求 else mui*primej = 0; break; /被篩掉的數(shù)都有素數(shù)的平方，被篩掉的數(shù)都有素數(shù)的平方， =0 2022-2-244、莫比烏斯函數(shù)性質、莫比烏斯函數(shù)性質-定理定理1 定理定理1：設設f(n)和和 F(n)均為定義在均為定義在N上的數(shù)論函數(shù)，上的

10、數(shù)論函數(shù)， f(n)不不恒為恒為0，若，若f(n)為積性函數(shù)，則為積性函數(shù)，則F(n)也為積性函數(shù)。也為積性函數(shù)。 證：設證：設n有標準分解有標準分解 已知已知 F(1)=f(1)=1。n的任一正因子的任一正因子d，可寫為，可寫為 因此因此2022-2-24kkpppn.2121ndekeendkpppfdfnF|21|).()()(21kekeepppd.2121kkkkeekeeeendekeepfpfpfpfpfpf00101|21)(.)()()().()(22111121)().()(2121kekeepFpFpF因此，因此，F(xiàn)(n)為積性函數(shù)為積性函數(shù)4、莫比烏斯函數(shù)性質、莫比烏斯

11、函數(shù)性質-定理定理2定理定理2：設設f(n)和和 F(n)均為定義在均為定義在N上的數(shù)論函數(shù)，上的數(shù)論函數(shù)，那么那么F(n)為為f(n)的莫比烏斯變換，即的莫比烏斯變換，即的充要條件是的充要條件是這里，這里， 為莫比烏斯函數(shù)，為莫比烏斯函數(shù)，2022-2-24nddfnF|)()(nddnFdnf|)()()()(dnddFdnnf|)()()(注：因注：因d遍歷遍歷n的所有因子，當且僅當，的所有因子，當且僅當， n/d遍歷遍歷n的所有因子。因此的所有因子。因此f(n)也可寫也可寫預備 對于對于 k|(n/d)，指有整數(shù)，指有整數(shù)q使得使得n/d=kq，即，即n=dkq 即即d|(n/k)，d

12、|n2022-2-24nddnkndkfddnFd|)()()()(nddfnF|)()(證明證明 必要性：必要性： 設設 成立，那么成立，那么2022-2-24nddfnF|)()(nddnkndkfddnFd|)()()()( nkkndndndkkdkfdkf|,)()()()()(/1 )()()(|nfknkfdkfnknkknd證明證明 充分性：充分性： 設設 成立，那么成立，那么 令令d=km，那么，那么2022-2-24nddnFdnf|)()()( nknddknddkndkdFkkdFkdf|,|)()()()()()(/1)()()()()()()()(|,|nFmnmF

13、kmFmFkkdFkdfnmnmmnknkknmnknddknd 3個特例之個特例之1、21. 設設f1(n)=n，那么，那么 為為n的所有正的所有正因子之和。因子之和。 如設如設 ，那么，那么 F1 (n)= 根據反演公式有根據反演公式有2. 設設f2(n)=1，那么，那么 為為n的所有的所有正因子個數(shù)正因子個數(shù)( 1+1)( 2+1) ( k+1)。 有類似反演公式，很神奇。有類似反演公式，很神奇。2022-2-24ndndddfnF|11)()(kkpppn.212111.1111121211121kkppppppkndnddfnF|221)()(nddnFdnfn|11)()()(20

14、22-2-243個個特例之特例之3 33. 若若f(n)是歐拉函數(shù)是歐拉函數(shù) (n)，則，則反演后反演后ndnFnd|)()(ndndddndndn|)()()(莫比烏斯變換的另一種有用形式莫比烏斯變換的另一種有用形式設設f(n)，F(xiàn)(n)為整數(shù)函數(shù)，為整數(shù)函數(shù)，1 n,d N。記。記那么有那么有證明：以下假定：證明：以下假定：n, d N 記記有有dndfnF|)()(dndFndnf|)()()(dndFndng|)()()(111|1)()()()()()()(nNiniNjnNidnidnNinijfidfiniFing滿足證明證明)()()()1()1(.)(.)3()2()()(.

15、)3().12()9()6()3()3()2().8()6()4()2()2()(.)4()3()2()1()1()()()(11nnNfnNnnNfnnNfnNnniNfnifnifnifinnNfnfnfnfnfnnNfnfnfnfnfnnNfnfnfnfnfnijfingnNiniNj歸類合并歸類合并證明證明這里利用了這里利用了)()1(.)()(.)4()4()2()1()3()3()1()2()2()1()1()1()(|nfnfnkfdnfnfnfnfngkd1011)(|kkdkd5、莫比烏斯函數(shù)應用、莫比烏斯函數(shù)應用- Eratosthenes篩法篩法 設設A=為整數(shù)序列（可重

16、復），記為整數(shù)序列（可重復），記d為為正整數(shù)，正整數(shù)， Ad= ， 用用|Ad|記序列記序列Ad中元素的個數(shù)。中元素的個數(shù)。 舉例：舉例： 如如A=，d=3，那么，那么A3=，元素個數(shù)為，元素個數(shù)為5.A7=，元素個數(shù)為，元素個數(shù)為3.2022-2-24定理定理3、Eratosthenes篩法篩法 定理定理3、設設m為正整數(shù)，為正整數(shù)， p1,p2,pt為為m的所有不同的所有不同的素因子。那么的素因子。那么 序列序列A中與中與m既約的整數(shù)的個數(shù)為既約的整數(shù)的個數(shù)為 證明：證明：已有結論已有結論 特別地，特別地， 因此因此2022-2-24 mddmdadAaAamdadAamadmaAaAdd

17、ddmAS|,|),|gcd(1),gcd(,|)(1)()()(1),(mddmaAaAdmAS|1),gcd(,|)(1),(10111)()(|nnndnInd1),gcd(01),gcd(1)(),|gcd(mamadmad舉例舉例-求不超過求不超過120的素數(shù)的個數(shù)的素數(shù)的個數(shù) 解：不超過解：不超過120的合數(shù)必是的合數(shù)必是2、3、5或或7的真倍數(shù)。記的真倍數(shù)。記m=2*3*5*7=210，記，記A=1.120，d|210，記，記Ad= a： d | a ，0a121，|Ad|=120/d2022-2-24d1235761014152135304270105210 (d)1-1-1-

18、1-1111111-1-1-1-11|Ad| 120 60 4024172012885342110 1到到120中與中與120既約的整數(shù)的個數(shù)為既約的整數(shù)的個數(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不既約，但是素不既約，但是素數(shù)。數(shù)。1不是素數(shù)。因此不超過不是素數(shù)。因此不超過120的素數(shù)的個數(shù)的素數(shù)的個數(shù)=27+4-1=30mddAdAS|)()120,(容斥原理與莫比烏斯變換對照容斥原理與莫比烏斯變換對照 兩個集合的容斥關系公式：兩個集合的容斥關系公式： AB =|AB| = |A

19、|+|B| - |AB |(：重合的部分）：重合的部分） 三個集合的容斥關系公式：三個集合的容斥關系公式： |ABC| = |A|+|B|+|C| - |AB| - |BC| - |CA| + |ABC| 一般地，設一般地，設S為有限集，為有限集，Ai S，則則2022-2-24|.|m21AAA思考思考 在在1到到1000的自然數(shù)中，能被的自然數(shù)中，能被3或或5整除的數(shù)共有多少個？整除的數(shù)共有多少個？不能被不能被3或或5整除的數(shù)共有多少個？整除的數(shù)共有多少個？ 解：略解：略 分母是分母是1001的最簡分數(shù)一共有多少個？的最簡分數(shù)一共有多少個？ 分析：這一題實際上就是找分子中不能與分析：這一題

20、實際上就是找分子中不能與1001進行約分的進行約分的數(shù)。由于數(shù)。由于1001=71113，所以就是找不能被，所以就是找不能被7，11，13整除的數(shù)。整除的數(shù)。 由容斥原理知：在由容斥原理知：在11001中，能被中，能被7或或11或或13整除的數(shù)有整除的數(shù)有（143+91+77）-（13+11+7）+1=281（個），從而不能被（個），從而不能被7、11或或13整除的數(shù)有整除的數(shù)有1001-281=720（個）（個）.也就是說，分母也就是說，分母為為1001的最簡分數(shù)有的最簡分數(shù)有720個。個。2022-2-24定理定理3推論推論 推論：設推論：設m為正整數(shù)，那么為正整數(shù)，那么 序列序列A中使中

21、使gcd(m, a)=k的整數(shù)的個數(shù)為的整數(shù)的個數(shù)為2022-2-24kmddkmkaAakmaAaAdkmAS|1),gcd(,),gcd(,|)(11),(序列序列A的幾種常見形式的幾種常見形式 設設A為整數(shù)的一個序列，為整數(shù)的一個序列，m為正整數(shù)。那么為正整數(shù)。那么1. 設設n為正整數(shù)，為正整數(shù)，A為為1到到n的自然數(shù)的序列。那么的自然數(shù)的序列。那么Ad=，|Ad|=n/d那么那么1到到n中與中與m互質的自然數(shù)的個數(shù)為互質的自然數(shù)的個數(shù)為 特別地，特別地， 1到到n中與中與n互質的自然數(shù)的個數(shù)為互質的自然數(shù)的個數(shù)為2022-2-24mddAdmAS| )(),(mddndmf|)()(n

22、dndddndndn|)()()(可用于求可用于求1到到n中素數(shù)個數(shù)中素數(shù)個數(shù)序列序列A的幾種常見形式的幾種常見形式2. 設設n為正整數(shù)，為正整數(shù)，A為為1到到n的所有自然數(shù)對的所有自然數(shù)對(a, b)的的gcd序列，即序列，即 A=，A共有共有n2個元素，個元素， Ad=，顯然，顯然 |Ad|=n/d n/d A中與中與m互質的自然數(shù)的個數(shù)為互質的自然數(shù)的個數(shù)為3. 設設A為為1到到n的所有自然數(shù)對的所有自然數(shù)對(a, b,c)的的gcd序列，那序列，那么么 |Ad|=n/d n/d n/d。A中與中與m互質的自然數(shù)互質的自然數(shù)的個數(shù)為的個數(shù)為2022-2-24)()(|dndndmfmd)

23、()(|dndndndmfmd注意：有許多重復的注意：有許多重復的例例1、公因數(shù)為質數(shù)問題、公因數(shù)為質數(shù)問題 http:/ 問題描述：問題描述：給一個正整數(shù)給一個正整數(shù)n，其中，其中n=107，求使得，求使得gcd(x,y)為質數(shù)的為質數(shù)的(x,y)的個數(shù)，（的個數(shù)，（1=x,y=n）。）。 分析：分析： 要使得一個數(shù)要使得一個數(shù)gcd(x,y)為質數(shù)，可枚舉小于等于為質數(shù)，可枚舉小于等于n的質數(shù)的質數(shù)p，那么對于每一個質數(shù)，只需要考慮在區(qū)間那么對于每一個質數(shù)，只需要考慮在區(qū)間1,n/p中，滿足序中，滿足序對對 (x,y)互質的對數(shù)?；ベ|的對數(shù)。 不妨設不妨設x y，那么如果枚舉每一個，那么如

24、果枚舉每一個y，小于，小于y有多少個有多少個x與與y互互素，這正是歐拉函數(shù)，即素，這正是歐拉函數(shù)，即 (y)。 所以可用遞推法求歐拉函數(shù)，將得到的答案乘以所以可用遞推法求歐拉函數(shù)，將得到的答案乘以2即可。但即可。但還有漏計算的，即還有漏計算的，即x=y且且y為素數(shù)的情況，再加上就行了。為素數(shù)的情況，再加上就行了。 參考代碼見下頁。參考代碼見下頁。2022-2-24#include #include using namespace std; typedef long long LL; const int N = 10000010; bitset prime; LL phiN, fN;int pN

25、, k; void isprime() /求素數(shù)組求素數(shù)組 k = 0; prime.set(); for(int i=2; iN; i+) if(primei) pk+ = i; for(int j=i+i; jN; j+=i)2022-2-24 primej = false; void Init() /求求 (i) int i,j; for( i=1; iN; i+) phii = i; for( i=2; i= 1; for( i=3; iN; i+=2) if(phii = i) for( j=i; jN; j+=i) phij = phij - phij / i; f1 = 0; f

26、or( i=2;iN;i+) fi = fi-1 + (phii1); LL Solve(int n) LL ans = 0; for(int i=0; ik&pi=n; i+) ans += 1 + fn/pi; return ans; int main() Init(); isprime(); int n; scanf(%d,&n); printf(%I64dn,Solve(n); return 0; 2022-2-24例例2、公因數(shù)為質數(shù)問題、公因數(shù)為質數(shù)問題-進一步進一步 http:/ 問題描述：問題描述：給定正整數(shù)給定正整數(shù)m, n，其中，其中n=107，求使得，求使

27、得gcd(x,y)為質數(shù)的為質數(shù)的(x,y)的個數(shù)，的個數(shù)，1=x=m， 1=y=n 。 分析：分析：用莫比烏斯反演來解決用莫比烏斯反演來解決。2022-2-24例解：記解：記A=； f(d)=| |，即，即A中使得中使得gcd(x,y)=d的數(shù)的個數(shù)。的數(shù)的個數(shù)。 再記再記 即即 F(k)是滿足是滿足 k | gcd(x,y)的數(shù)對的數(shù)對(x, y)的個數(shù)。的個數(shù)。那么，顯然那么，顯然根據反演公式根據反演公式dkdfkF|)()()(kmknkFdkdmdnkdkf|)()(dkdFkdkf|)()()( 題目要求gcd(x,y)為質數(shù)，那么我們枚舉每一個質數(shù)q，然后得到 本題需要優(yōu)化),m

28、in(1),min()()(mnimnpppimpinipfresult質數(shù)質數(shù)用Eratosthenes篩法的嘗試篩法的嘗試 設設A為為a在在1, m，b在在1, n的所有自然數(shù)對的所有自然數(shù)對(x, y)的的gcd序列序列，即，即 A=，A共有共有mn個個元素，元素， Ad=，顯，顯然然 |Ad|=m/d n/d2022-2-24分析分析 對于正整數(shù)對于正整數(shù)q， 序列序列A中與中與q互質的整數(shù)互質的整數(shù)a的個數(shù)為的個數(shù)為 題目要求題目要求gcd(x, y)是質數(shù)，現(xiàn)枚舉每一個質數(shù)是質數(shù)，現(xiàn)枚舉每一個質數(shù)q。 對于固定的質數(shù)對于固定的質數(shù)q，序列，序列A中使與中使與q不互質的整數(shù)不互質的整

29、數(shù)a就就是使得是使得gcd(x, y)=q的數(shù)，個數(shù)為的數(shù)，個數(shù)為mn-Sq。 因此，序列因此，序列A中為質數(shù)的整數(shù)中為質數(shù)的整數(shù)a個數(shù)為個數(shù)為2022-2-24qddqaAaqAdS|1),gcd(,|)(1),min()(nmqqSmn素數(shù)例例3、Mophues Source：http:/ Description: 任何整數(shù)任何整數(shù)C ( C = 2 )都可以寫成素數(shù)之積都可以寫成素數(shù)之積C = p1p2 p3 . pk其中，其中， p1, p2 . pk 是素數(shù)。如是素數(shù)。如 C = 24, 則則 24 = 2 2 2 3, 其中其中, p1 = p2 = p3 = 2, p4 = 3,

30、 k = 4.給定兩整數(shù)給定兩整數(shù) P和和 C, 若若 k=P ( k是是 C的素因子個數(shù)的素因子個數(shù)),稱稱 C是是P的幸的幸運數(shù)運數(shù).現(xiàn)小現(xiàn)小X需計算的點對需計算的點對 (a, b)的個數(shù)的個數(shù),其中其中1=a=n , 1=b=m, gcd(a,b)是是 P的幸運數(shù)的幸運數(shù) ( “gcd”是最大公因數(shù)是最大公因數(shù)).注意：因為注意：因為1無素因子，定義無素因子，定義1為任何非負數(shù)的幸運數(shù)為任何非負數(shù)的幸運數(shù).2022-2-24 Input 首行有一個整數(shù)首行有一個整數(shù) T，表示有，表示有 T 組測試數(shù)據組測試數(shù)據.接下來有接下來有T行，行，每行是一種測試數(shù)據，含每行是一種測試數(shù)據，含3個非

31、負整數(shù)個非負整數(shù)n, m 與與P (n, m, P = 5105. T =5000). Output 對每種測試數(shù)據，輸出對對每種測試數(shù)據，輸出對 (a, b)的個數(shù)，其中的個數(shù)，其中 1=a=n , 1=b=m, 且且 gcd(a,b) 是是 P的幸運數(shù)的幸運數(shù).2022-2-24Sample Input210 10 010 10 1Sample Output6393Mophues分析分析 題意：給出題意：給出n, m, p，求求(a, b)的對數(shù)：滿足的對數(shù)：滿足 gcd(a, b)的素的素因子個數(shù)因子個數(shù)=p，(其中其中1=a=n, 1=b=m) 分析：設分析：設f(d)：gcd(a,

32、b)=d的的(a,b)的組數(shù)，的組數(shù)， F(k): k| gcd(a, b) 的的(a,b)的組數(shù)，的組數(shù)， 易知易知F(k) = n/k*m/k；dkdmdnkdkf|)()(對整數(shù)對整數(shù)k，枚舉，枚舉k的素因子個數(shù)使得總數(shù)的素因子個數(shù)使得總數(shù)=p，這種，這種k記作記作k(p)k(p)=k，當，當k的素因子個數(shù)不超過的素因子個數(shù)不超過pk(p)=0，當，當k的素因子個數(shù)超過的素因子個數(shù)超過p。dkpkpkdmdnkdkfresult|)()()()(程序實現(xiàn)：見下頁程序實現(xiàn)：見下頁dkkdkf|F(d)()(dkdfkF|)()(include #include #include using

33、 namespace std; const int M = 555555, int N = 19; int gMN, numM; int priM,pnum,muM,visM; int calc(int y,int x) /統(tǒng)計統(tǒng)計y中因子中因子x出現(xiàn)的次數(shù)出現(xiàn)的次數(shù) int ret = 0; while(y%x=0) ret+; y /= x; return ret; 2022-2-24int main() int T,n,m,P, i, j; init(); cinT; while(T-) cinnmP; long long ans = 0; if(P = N) cout (long lo

34、ng) n * m m) swap(n,m); for( i = 1;i = n;i = j+1) j = min(n/(n/i) , m/(m/i); ans += (long long)gjP - gi-1P)*(n/i)*(m/i); cout ans endl; return 0; void init() /計算計算 (d)的值的值int n = M-1; memset(num,0,sizeof(num); memset(g,0,sizeof(f); memset(mu,0,sizeof(mu); memset(vis,0,sizeof(vis); pnum=0; vis1 = mu1

35、 = 1; for(int i = 2;i = n;i+) if(!visi)pripnum+=i; mui=-1; for(int j = 0;j n) break; visi*prij = 1; if(i % prij = 0) mui*prij = 0; break; mui*prij = -mui; 2022-2-24for(int i = 2; i = n;i+) if(numi=0) for(int j = i; j = n;j+=i) numj += calc(j,i); for(int i = 1;i = n;i+) for(int j = i;j = n; j+=i)gjnu

36、mi += muj/i; for(int i = 1;i = n;i+) for(int j = 1;j N;j+)gij += gij-1; for(int i = 1;i = n;i+) for(int j = 0;j N;j+) gij += gi-1j; 注：注：numj記錄記錄j的因子數(shù)。的因子數(shù)。 gjnumi用于計算具有相同個數(shù)的素因子的用于計算具有相同個數(shù)的素因子的i的的 (j/i)之之和，和，2022-2-24例例4、可見格點、可見格點 Soucee：SPOJ 7001Description 有有 N*N*N網格網格. 一個角落在一個角落在 (0,0,0)，對頂角落是，對頂角

37、落是 (N,N,N). 問從問從(0,0,0)看有多少個格點是可見的？點看有多少個格點是可見的？點 X從點從點Y可見，可見，當且僅當，線段當且僅當，線段XY上沒有其他的點。上沒有其他的點。Input: 第一行是測試數(shù)據個數(shù)第一行是測試數(shù)據個數(shù)T。接著有。接著有T行每行有一個整數(shù)行每行有一個整數(shù) N. Output : 輸出輸出T行，每行是對應的可見格點的個數(shù)。行，每行是對應的可見格點的個數(shù)。2022-2-24Sample Input : 3 1 2 5 Sample Output : 7 19 175 Constraints : T = 50 1 = N = 10000002022-2-24可見格點可見格點-分析分析 本題要求使本題要求使gcd(a,b,c) = 1且且 a,b,c =N 的的(a,b,c)的數(shù)對總數(shù)。的數(shù)對總數(shù)。 用莫比烏斯反演可以求解。用