莫比烏斯變換ppt課件.ppt

莫比烏斯變換 1 引言莫比烏斯變換 1 復平面上的莫比烏斯變換公元1858年 德國數(shù)學家莫比烏斯 Mobius 1790 1868 發(fā)現(xiàn) 把一個扭轉(zhuǎn)180 后再兩頭粘接起來的紙條 具有魔術般的性質(zhì) 這樣的紙帶只有一個面 即單側曲面 一只小蟲可以爬遍整個曲面而不必跨過它的邊緣 這種由莫比烏斯發(fā)現(xiàn)的神奇的單面紙帶 稱為 莫比烏斯帶 幾何學中的莫比烏斯變換 其中z a b c d為復數(shù)且滿足ad bc 0 1 引言莫比烏斯變換 2 數(shù)論中的莫比烏斯變換對于給定的數(shù)論函數(shù)f n n N 定義新的數(shù)論函數(shù)稱F n 為f n 的莫比烏斯變換 而f n 為F n 的莫比烏斯逆變換 2 數(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 莫比烏斯逆變換計算實例 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 的項 引入莫比烏斯函數(shù) n 記 d 為 F n d 的符號 或 之一有 1 6 1 2 3 5 7 1 4 8 0 若p是素數(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ù)推下去 有當k 1 有 pk 0 莫比烏斯函數(shù) n 繼續(xù)觀察 設p1 p2為不同素數(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 總結得 積性函數(shù) 積性函數(shù)f n 對數(shù)論函數(shù)f n 如果滿足對任意正整數(shù)m n 只要gcd m n 1 就有f mn f m f n 那么稱f n 為積性函數(shù)完全積性函數(shù)g n 對數(shù)論函數(shù)g n 如果滿足對任意正整數(shù)m n 均有g 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 對于f n 1的特例 證明 首先 n 是積性函數(shù) 因此用下面將證明的一個命題可知I n 也是積性函數(shù) 顯然 I 1 1 而對素數(shù)p I pt 1 p p2 pt 1 1 0 0 0 證畢 計算莫比烏斯函數(shù)的程序?qū)崿F(xiàn) voidMobius 計算d的不同素因子個數(shù) 計算 d 的值memset vis 0 sizeof vis vis i 記錄記錄i是否標記過mu 1 1 cnt 0 for inti 2 i N i if vis i 如果vis i 是第1個未標記的 那么i是素數(shù)prime cnt i mu i 1 for intj 0 j cnt 被篩掉的數(shù)都有素數(shù)的平方 0 4 莫比烏斯函數(shù)性質(zhì) 定理1 定理1 設f n 和F n 均為定義在N上的數(shù)論函數(shù) f n 不恒為0 若f n 為積性函數(shù) 則F n 也為積性函數(shù) 證 設n有標準分解已知F 1 f 1 1 n的任一正因子d 可寫為因此 因此 F n 為積性函數(shù) 4 莫比烏斯函數(shù)性質(zhì) 定理2 定理2 設f n 和F n 均為定義在N上的數(shù)論函數(shù) 那么F n 為f n 的莫比烏斯變換 即的充要條件是這里 為莫比烏斯函數(shù) 注 因d遍歷n的所有因子 當且僅當 n d遍歷n的所有因子 因此f n 也可寫 預備 對于k n d 指有整數(shù)q使得n d kq 即n dkq即d n k d n 證明 必要性 設成立 那么 證明 充分性 設成立 那么令d km 那么 3個特例之1 2 設f1 n n 那么為n的所有正因子之和 如設 那么F1 n 根據(jù)反演公式有設f2 n 1 那么為n的所有正因子個數(shù) 1 1 2 1 k 1 有類似反演公式 很神奇 3個特例之3 若f n 是歐拉函數(shù) n 則反演后 莫比烏斯變換的另一種有用形式 設f n F n 為整數(shù)函數(shù) 1 n d N 記那么有證明 以下假定 n d N記有 證明 歸類合并 證明 這里利用了 5 莫比烏斯函數(shù)應用 Eratosthenes篩法 設A 為整數(shù)序列 可重復 記d為正整數(shù) Ad 用 Ad 記序列Ad中元素的個數(shù) 舉例 如A d 3 那么A3 元素個數(shù)為5 A7 元素個數(shù)為3 定理3 Eratosthenes篩法 定理3 設m為正整數(shù) p1 p2 pt為m的所有不同的素因子 那么序列A中與m既約的整數(shù)的個數(shù)為證明 已有結論特別地 因此 舉例 求不超過120的素數(shù)的個數(shù) 解 不超過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ù)的個數(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ù) 1不是素數(shù) 因此不超過120的素數(shù)的個數(shù) 27 4 1 30 容斥原理與莫比烏斯變換對照 兩個集合的容斥關系公式 A B A B A B A B 重合的部分 三個集合的容斥關系公式 A B C A B C A B B C C A A B C 一般地 設S為有限集 Ai S 則 思考 在1到1000的自然數(shù)中 能被3或5整除的數(shù)共有多少個 不能被3或5整除的數(shù)共有多少個 解 略分母是1001的最簡分數(shù)一共有多少個 分析 這一題實際上就是找分子中不能與1001進行約分的數(shù) 由于1001 7 11 13 所以就是找不能被7 11 13整除的數(shù) 由容斥原理知 在1 1001中 能被7或11或13整除的數(shù)有 143 91 77 13 11 7 1 281 個 從而不能被7 11或13整除的數(shù)有1001 281 720 個 也就是說 分母為1001的最簡分數(shù)有720個 定理3推論 推論 設m為正整數(shù) 那么序列A中使gcd m a k的整數(shù)的個數(shù)為 序列A的幾種常見形式 設A為整數(shù)的一個序列 m為正整數(shù) 那么設n為正整數(shù) A為1到n的自然數(shù)的序列 那么Ad Ad n d 那么1到n中與m互質(zhì)的自然數(shù)的個數(shù)為特別地 1到n中與n互質(zhì)的自然數(shù)的個數(shù)為 可用于求1到n中素數(shù)個數(shù) 序列A的幾種常見形式 設n為正整數(shù) A為1到n的所有自然數(shù)對 a b 的gcd序列 即A A共有n2個元素 Ad 顯然 Ad n d n d A中與m互質(zhì)的自然數(shù)的個數(shù)為設A為1到n的所有自然數(shù)對 a b c 的gcd序列 那么 Ad n d n d n d A中與m互質(zhì)的自然數(shù)的個數(shù)為 注意 有許多重復的 例1 公因數(shù)為質(zhì)數(shù)問題 問題描述 給一個正整數(shù)n 其中n 107 求使得gcd x y 為質(zhì)數(shù)的 x y 的個數(shù) 1 x y n 分析 要使得一個數(shù)gcd x y 為質(zhì)數(shù) 可枚舉小于等于n的質(zhì)數(shù)p 那么對于每一個質(zhì)數(shù) 只需要考慮在區(qū)間 1 n p 中 滿足序?qū)?x y 互質(zhì)的對數(shù) 不妨設x y 那么如果枚舉每一個y 小于y有多少個x與y互素 這正是歐拉函數(shù) 即 y 所以可用遞推法求歐拉函數(shù) 將得到的答案乘以2即可 但還有漏計算的 即x y且y為素數(shù)的情況 再加上就行了 參考代碼見下頁 include includeusingnamespacestd typedeflonglongLL constintN 10000010 bitsetprime LLphi N f N intp N k voidisprime 求素數(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ù)問題 進一步 問題描述 給定正整數(shù)m n 其中n 107 求使得gcd x y 為質(zhì)數(shù)的 x y 的個數(shù) 1 x m 1 y n 分析 用莫比烏斯反演來解決 例 解 記A f d 即A中使得gcd x y d的數(shù)的個數(shù) 再記即F k 是滿足k gcd x y 的數(shù)對 x y 的個數(shù) 那么 顯然根據(jù)反演公式 題目要求gcd x y 為質(zhì)數(shù) 那么我們枚舉每一個質(zhì)數(shù)q 然后得到本題需要優(yōu)化 用Eratosthenes篩法的嘗試 設A為a在 1 m b在 1 n 的所有自然數(shù)對 x y 的gcd序列 即A A共有mn個元素 Ad 顯然 Ad m d n d 分析 對于正整數(shù)q 序列A中與q互質(zhì)的整數(shù)a的個數(shù)為題目要求gcd x y 是質(zhì)數(shù) 現(xiàn)枚舉每一個質(zhì)數(shù)q 對于固定的質(zhì)數(shù)q 序列A中使與q不互質(zhì)的整數(shù)a就是使得gcd x y q的數(shù) 個數(shù)為mn Sq 因此 序列A中為質(zhì)數(shù)的整數(shù)a個數(shù)為 例3 Mophues Source Description 任何整數(shù)C C 2 都可以寫成素數(shù)之積C p1 p2 p3 pk其中 p1 p2 pk是素數(shù) 如C 24 則24 2 2 2 3 其中 p1 p2 p3 2 p4 3 k 4 給定兩整數(shù)P和C 若k P k是C的素因子個數(shù) 稱C是P的幸運數(shù) 現(xiàn)小X需計算的點對 a b 的個數(shù) 其中1 a n 1 b m gcd a b 是P的幸運數(shù) gcd 是最大公因數(shù) 注意 因為1無素因子 定義1為任何非負數(shù)的幸運數(shù) Input首行有一個整數(shù)T 表示有T組測試數(shù)據(jù) 接下來有T行 每行是一種測試數(shù)據(jù) 含3個非負整數(shù)n m與P n m P 5 105 T 5000 Output對每種測試數(shù)據(jù) 輸出對 a b 的個數(shù) 其中1 a n 1 b m 且gcd a b 是P的幸運數(shù) SampleInput21010010101SampleOutput6393 Mophues分析 題意 給出n m p 求 a b 的對數(shù) 滿足gcd a b 的素因子個數(shù) p 其中1 a n 1 b m 分析 設f d gcd a b d的 a b 的組數(shù) F k k gcd a b 的 a b 的組數(shù) 易知F k n k m k 對整數(shù)k 枚舉k的素因子個數(shù)使得總數(shù) p 這種k記作k p k p k 當k的素因子個數(shù)不超過pk p 0 當k的素因子個數(shù)超過p 程序?qū)崿F(xiàn) 見下頁 include include includeusingnamespacestd constintM 555555 intN 19 intg M N num M intpri M pnum mu M vis M intcalc inty intx 統(tǒng)計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 計算 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 用于計算具有相同個數(shù)的素因子的i的 j i 之和 例4 可見格點 Soucee SPOJ7001Description有N N N網(wǎng)格 一個角落在 0 0 0 對頂角落是 N N N 問從 0 0 0 看有多少個格點是可見的 點X從點Y可見 當且僅當 線段XY上沒有其他的點 Input 第一行是測試數(shù)據(jù)個數(shù)T 接著有T行每行有一個整數(shù)N Output 輸出T行 每行是對應的可見格點的個數(shù) SampleInput 3125SampleOutput 719175Constraints T 501 N 1000000 可見格點 分析 本題要求使gcd a b c 1且a b c N的 a b c 的數(shù)對總數(shù) 用莫比烏斯反演可以求解 設f n 為gcd a b c n的數(shù)對 a b c 組數(shù) 記即F k 為k gcd a b c 的 a b c 組數(shù) 那么F k N k