莫比烏斯變換ppt課件.ppt

莫比烏斯變換 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 bc 0 1 引言莫比烏斯變換 2 數(shù)論中的莫比烏斯變換對(duì)于給定的數(shù)論函數(shù)f n n N 定義新的數(shù)論函數(shù)稱F n 為f n 的莫比烏斯變換 而f n 為F n 的莫比烏斯逆變換 2 數(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 莫比烏斯逆變換計(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 3 逆變換與莫比烏斯函數(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 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 莫比烏斯函數(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 莫比烏斯函數(shù) n 總結(jié)得 積性函數(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ù) 莫比烏斯函數(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 證畢 計(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 被篩掉的數(shù)都有素?cái)?shù)的平方 0 4 莫比烏斯函數(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 可寫為因此 因此 F n 為積性函數(shù) 4 莫比烏斯函數(shù)性質(zhì) 定理2 定理2 設(shè)f n 和F n 均為定義在N上的數(shù)論函數(shù) 那么F n 為f n 的莫比烏斯變換 即的充要條件是這里 為莫比烏斯函數(shù) 注 因d遍歷n的所有因子 當(dāng)且僅當(dāng) n d遍歷n的所有因子 因此f n 也可寫 預(yù)備 對(duì)于k n d 指有整數(shù)q使得n d kq 即n dkq即d n k d n 證明 必要性 設(shè)成立 那么 證明 充分性 設(shè)成立 那么令d km 那么 3個(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 有類似反演公式 很神奇 3個(gè)特例之3 若f n 是歐拉函數(shù) n 則反演后 莫比烏斯變換的另一種有用形式 設(shè)f n F n 為整數(shù)函數(shù) 1 n d N 記那么有證明 以下假定 n d N記有 證明 歸類合并 證明 這里利用了 5 莫比烏斯函數(shù)應(yīng)用 Eratosthenes篩法 設(shè)A 為整數(shù)序列 可重復(fù) 記d為正整數(shù) Ad 用 Ad 記序列Ad中元素的個(gè)數(shù) 舉例 如A d 3 那么A3 元素個(gè)數(shù)為5 A7 元素個(gè)數(shù)為3 定理3 Eratosthenes篩法 定理3 設(shè)m為正整數(shù) p1 p2 pt為m的所有不同的素因子 那么序列A中與m既約的整數(shù)的個(gè)數(shù)為證明 已有結(jié)論特別地 因此 舉例 求不超過(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 d 1到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為有限集 Ai S 則 思考 在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è) 定理3推論 推論 設(shè)m為正整數(shù) 那么序列A中使gcd m a k的整數(shù)的個(gè)數(shù)為 序列A的幾種常見(jiàn)形式 設(shè)A為整數(shù)的一個(gè)序列 m為正整數(shù) 那么設(shè)n為正整數(shù) A為1到n的自然數(shù)的序列 那么Ad Ad n d 那么1到n中與m互質(zhì)的自然數(shù)的個(gè)數(shù)為特別地 1到n中與n互質(zhì)的自然數(shù)的個(gè)數(shù)為 可用于求1到n中素?cái)?shù)個(gè)數(shù) 序列A的幾種常見(jiàn)形式 設(shè)n為正整數(shù) A為1到n的所有自然數(shù)對(duì) a b 的gcd序列 即A A共有n2個(gè)元素 Ad 顯然 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ù)為 注意 有許多重復(fù)的 例1 公因數(shù)為質(zhì)數(shù)問(wèn)題 問(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è)x y 那么如果枚舉每一個(gè)y 小于y有多少個(gè)x與y互素 這正是歐拉函數(shù) 即 y 所以可用遞推法求歐拉函數(shù) 將得到的答案乘以2即可 但還有漏計(jì)算的 即x y且y為素?cái)?shù)的情況 再加上就行了 參考代碼見(jiàn)下頁(yè) include includeusingnamespacestd typedeflonglongLL constintN 10000010 bitsetprime 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 prime j false voidInit 求 i inti j for i 1 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 例2 公因數(shù)為質(zhì)數(shù)問(wèn)題 進(jìn)一步 問(wèn)題描述 給定正整數(shù)m n 其中n 107 求使得gcd x y 為質(zhì)數(shù)的 x y 的個(gè)數(shù) 1 x m 1 y n 分析 用莫比烏斯反演來(lái)解決 例 解 記A f d 即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 A共有mn個(gè)元素 Ad 顯然 Ad m d n d 分析 對(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ù)為 例3 Mophues Source Description 任何整數(shù)C C 2 都可以寫成素?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ù) Input首行有一個(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ù) SampleInput21010010101SampleOutput6393 Mophues分析 題意 給出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 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 include includeusingnamespacestd 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 intmain intT n m P i j init cin T while T cin n m P longlongans 0 if P N coutm s 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 in break vis i pri j 1 if i pri j 0 mu i pri j 0 break mu i pri j mu i 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 之和 例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ù) SampleInput 3125SampleOutput 719175Constraints T 501 N 1000000 可見(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