莫比烏斯變換-1-經(jīng)典形式與狄利克雷卷積

經(jīng)典形式

f 定義在正整數(shù)集合上埃唯,如果:

g(n) = \sum_{d|n} f(d), n \ge 1

g 稱作是 f和函數(shù)[1]琢蛤。

此時,無論 f 是什么蜂嗽,都有如下公式成立:

f(n) = \sum_{d|n} \mu(d) g(\frac{n}pjrnlpz), n \ge 1

其中的 \mu 是一個數(shù)論函數(shù)苗膝,稱作莫比烏斯函數(shù)

觀察這兩個式子植旧,前者由 f 求得 g辱揭;后者反過來由 g 求得 f。后者應用在求 gf 容易的情況下病附,用和函數(shù)反過來求原函數(shù)问窃。這種過程一般稱作莫比烏斯變換或者莫比烏斯反演

狄利克雷卷積

經(jīng)典表示方法雖然直接完沪,但是顯得繁瑣域庇。最常見的替代表示方案是使用狄利克雷卷積嵌戈。

f, g 都是定義在正整數(shù)集合上的函數(shù),他們的狄利克雷卷積是一個定義在同樣范圍內(nèi)的函數(shù)听皿,用 f*g 表示熟呛,滿足:

(f*g)(n) = \sum_{d|n} f(d) g(\frac{n}n1n9fh3)

或者寫成:

(f*g)(n) = \sum_{ab=n} f(a) g(b)

其中 a,b 是正整數(shù)。

從定義中顯然可以看出 * 運算滿足的交換律:f*g = g*f[2]尉姨。也可以看出它滿足結(jié)合定律 (f * g) * h = f * (g * h)庵朝。

下面取一些特殊函數(shù)做狄利克雷卷積。

\varepsilon(n)n=1 時為 1啊送,否則為 0偿短。那么 f*\varepsilon = f

1(n) = 1馋没,那么 (f*1)(n) = \sum_{d|n}f(d)1(.) = \sum_{d|n}f(d)昔逗,是 f 的和函數(shù)。

用狄利克雷卷積篷朵,莫比烏斯反演可以這樣表達:

如果 g = f*1勾怒,那么 f=g*\mu

莫比烏斯函數(shù)

在上面的反演表達中声旺,如果令 f = \varepsilon笔链,那么得到:

\varepsilon = 1 * \mu

這個表達式是對 \mu 更直接的描述。如果 \mu 滿足 \varepsilon = 1 * \mu腮猖,那么輕松可以證明 f = g * \mug * \mu = f * 1 * \mu = f * \varepsilon = f鉴扫。所以,證明莫比烏斯反演成立的工作量澈缺,也就只有根據(jù) \varepsilon = 1 * \mu 求出 \mu 的工作量坪创。


  1. 實際上,有很多種和函數(shù)的定義姐赡,這里只取這一種莱预。 ?

  2. 這里以定義域、值域分別相同项滑,并且同樣的輸入得到同樣的輸出依沮,來表達函數(shù)相等。 ?

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末枪狂,一起剝皮案震驚了整個濱河市危喉,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌州疾,老刑警劉巖姥饰,帶你破解...
    沈念sama閱讀 217,657評論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異孝治,居然都是意外死亡,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,889評論 3 394
  • 文/潘曉璐 我一進店門谈飒,熙熙樓的掌柜王于貴愁眉苦臉地迎上來岂座,“玉大人,你說我怎么就攤上這事杭措》咽玻” “怎么了?”我有些...
    開封第一講書人閱讀 164,057評論 0 354
  • 文/不壞的土叔 我叫張陵手素,是天一觀的道長鸳址。 經(jīng)常有香客問我,道長泉懦,這世上最難降的妖魔是什么稿黍? 我笑而不...
    開封第一講書人閱讀 58,509評論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮崩哩,結(jié)果婚禮上巡球,老公的妹妹穿的比我還像新娘。我一直安慰自己邓嘹,他們只是感情好酣栈,可當我...
    茶點故事閱讀 67,562評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著汹押,像睡著了一般矿筝。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上棚贾,一...
    開封第一講書人閱讀 51,443評論 1 302
  • 那天窖维,我揣著相機與錄音,去河邊找鬼鸟悴。 笑死陈辱,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的细诸。 我是一名探鬼主播沛贪,決...
    沈念sama閱讀 40,251評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼震贵!你這毒婦竟也來了利赋?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,129評論 0 276
  • 序言:老撾萬榮一對情侶失蹤猩系,失蹤者是張志新(化名)和其女友劉穎媚送,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體寇甸,經(jīng)...
    沈念sama閱讀 45,561評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡塘偎,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,779評論 3 335
  • 正文 我和宋清朗相戀三年疗涉,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片吟秩。...
    茶點故事閱讀 39,902評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡咱扣,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出涵防,到底是詐尸還是另有隱情闹伪,我是刑警寧澤,帶...
    沈念sama閱讀 35,621評論 5 345
  • 正文 年R本政府宣布壮池,位于F島的核電站偏瓤,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏椰憋。R本人自食惡果不足惜厅克,卻給世界環(huán)境...
    茶點故事閱讀 41,220評論 3 328
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望熏矿。 院中可真熱鬧已骇,春花似錦、人聲如沸票编。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,838評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽慧域。三九已至鲤竹,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間昔榴,已是汗流浹背辛藻。 一陣腳步聲響...
    開封第一講書人閱讀 32,971評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留互订,地道東北人吱肌。 一個月前我還...
    沈念sama閱讀 48,025評論 2 370
  • 正文 我出身青樓,卻偏偏與公主長得像仰禽,于是被迫代替她去往敵國和親氮墨。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,843評論 2 354

推薦閱讀更多精彩內(nèi)容

  • 提示:別用莫比烏斯反演公式吐葵,會炸的 只需要記坠婢尽: [gcd(i,j)=1]=\sum_{d|gcd(i,j)}\m...
    An_Account閱讀 1,910評論 0 0
  • (一) 在我出嫁那天,我媽說我爸哭了温峭。 婚禮恰好進行到“感恩父母”環(huán)節(jié)猛铅,主持人大喊“擁抱父母”。我擁抱了爸媽很久很...
    小維維_d991閱讀 908評論 1 5
  • 回顧上一周的互聯(lián)網(wǎng)月杉,出現(xiàn)了不少事件刃跛,如百度再次出手收購一家90后公司渡鴉,并把度秘團隊升級為度秘事業(yè)部苛萎,均直接向陸...
    孫凌聊校園閱讀 328評論 0 13
  • 【小引】 工作之后,很少聽到周圍人說誰誰誰過世了检号,大概是周圍人基本都在退休年齡之前腌歉,要過世就算英年早逝。 漸漸的似...
    蘇三州閱讀 271評論 1 1