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