數論狄利克雷卷積 & 莫比烏斯反演

上一場 Div.2 的比賽中出了這題要用到莫比烏斯函數來做排容

不過這兩個東西都是之前就聽過，但從來沒有真的去了解過這東西

最近就決定來好好這兩個可怕的數學

如果只是想要知道如何使用莫比烏斯反演計算題目，則可跳過證明的部分

積性函數

在學狄利克雷卷積前，我們要先知道什麼是積性函數，積性函數的定義為以下

\(f(1) = 1\)
\(gcd(a,b) = 1 \Rightarrow f(ab) = f(a)f(b)\)

因此當 \(n = p_1^{k_1} p_2^{k_2} \cdots\) 時，\(f(n) = f(p_1^{k_1}) f(p_2^{k_2})\cdots\)

而常見的積性函數有以下幾個

歐拉函數 \(\varphi(n)\) : 小於 \(n\) 且與 \(n\) 互質的數字數量
莫比烏斯函數 \(\mu(n)\)

\(\mu(n) = \begin{cases} 1&, \text{when } n = 1\\(-1)^k &,\text{when } n \text{ does not have a squared prime factor and } n = p_1p_2\cdots p_k \\ 0 & ,\text{when } n \text{ has a squared prime factor}\end{cases}\)

特定數字 \(k\) 的最大公因數 \(gcd(n,k)\)
除數函數 \(\displaystyle \sigma_k(n) = \sum_{d|n}d^k\)，而 \(\sigma_0(n)\) 為數字的因數數量， \(\sigma_1(n)\) 為數字的因數之和
常數函數 \(1(n) = 1\)
冪函數 \(\text{Id}_k(n) = n^k\)，恆等函數 \(\text{Id}(n) = n\)

這些函數皆可以利用線性篩在 \(O(n)\) 時間內求出

狄利克雷卷積

我們定義一種對於數論函數(定義域為 \(\mathbb{Z} \rightarrow \mathbb{C}\)的函數)的一種運算，使得

\[ (f * g)(n) = \sum_{xy = n} f(x) g(y) = \sum_{d|n} f(d) g(\frac{n}{d})\]

而這個運算，我們就將其稱為「狄利克雷卷積」

將這個運算做為數論函數的乘法運算，一般函數的加法作為加法運算，就會使得數論函數形成一個交換環 (滿足交換律)

性質一、若 \(f\) 與 \(g\) 皆為積性函數，則 \(f * g\) 同樣為積性函數

證明:

首先，\((f*g)(1) = f(1)g(1) = 1\)

假設 \(a, b\) 互質，則有以下式子

\(\displaystyle (f*g)(a) = \sum_{d|a}f(d)g(\frac{a}{d})\) (1)

\(\displaystyle (f*g)(b) = \sum_{d|b}f(d)g(\frac{b}{d})\) (2)

\(\displaystyle (f*g)(ab) = \sum_{d|ab}f(d)g(\frac{ab}{d})\) (3)

將 (1), (2) 式相乘，得 \[\displaystyle (f*g)(a) \cdot (f*g)(b) = \sum_{d|a}f(d)g(\frac{a}{d}) \sum_{d|b}f(d)g(\frac{b}{d})\] \[= \sum_{d_1|a, d_2|b} f(d_1)g(\frac{a}{d_1})f(d_2)g(\frac{b}{d_2})\] \[= \sum_{d_1|a, d_2|b} f(d_1 d_2) g(\frac{ab}{d_1 d_2})\] \[= \sum_{d | ab} f(d) g(\frac{ab}{d})\]

因此得證

\((f * g)\) 滿足當 \((f * g)(1) = 1\)

且當 \(a,b\) 兩數互質時，\((f*g)(a) \cdot (f*g)(b) = (f*g)(ab)\)

因此 \((f * g)\) 為積性函數

性質二、滿足交換律 \(f * g = g * f\)

證明:

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

令 \(\displaystyle d' = \frac{n}{d} \Rightarrow d = \frac{n}{d'}\)，則上式可寫為

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

性質三、滿足結合律 \((f * g) * h = f * (g * h)\)

證明:

\[\displaystyle ((f * g) * h)(n) = \sum_{d|n} (f*g)(d) h(\frac{n}{d})\] \[\displaystyle = \sum_{d_1|n}\sum_{d_2|d_1} f(d_2) g(\frac{d_1}{d_2}) h(\frac{n}{d_1})\] \[\displaystyle = \sum_{d_1|n}\sum_{d_2|d_1} f(d_2) g(\frac{d_1}{d_2}) h(\frac{n}{d_1})\] \[\displaystyle = \sum_{d_1 d_1' = n}\sum_{d_2 d_2' = d_1} f(d_2) g(d_2') h(d_1')\] \[\displaystyle = \sum_{d_2 d_2' d_1' = n} f(d_2) g(d_2') h(d_1')\] \[\displaystyle = \sum_{d_2 d_2' d_1' = n} f(d_1') g(d_2) h(d_2')\] \[\displaystyle = \sum_{d_2 d_2' d_1' = n} f(d_1') (g*h)(d_1)\] \[\displaystyle = f * (g * h) (n)\]

性質四、滿足分配律 \(f * (g+h) = f * g + f * h\)

證明:

\[\displaystyle f * (g+h)(n) = \sum_{d|n} f(d) (g+h)(\frac{n}{d})\]

\[\displaystyle = \sum_{d|n} f(d) (g(\frac{n}{d})+h(\frac{n}{d}))\]

\[\displaystyle = \sum_{d|n} f(d)g(\frac{n}{d})+f(d)h(\frac{n}{d})\]

\[\displaystyle = \sum_{d|n} f(d)g(\frac{n}{d})+\sum_{d|n} f(d)h(\frac{n}{d})\]

\[\displaystyle = f*g + g*h\]

性質五、存在一單位函數 \(\varepsilon\)，使得 \(f * \varepsilon = \varepsilon * f = f\)

\[\varepsilon(n) = \begin{cases} 1 &, \text{when } n = 1 \\ 0 & , \text{when } n \ne 1\end{cases}\]

性質六、對於每個數論函數 \(f\)，皆有一個反函數 \(f^{-1}\)，使得 \(f * f^{-1} = \varepsilon\)

對於 \(f\) 的反函數

當 \(n = 1\) 時，\(\displaystyle f^{-1}(1) = \frac{1}{f(1)} = \varepsilon(1) = 1\)

當 \(n \ne 1\) 時， \(\displaystyle f(n) * f^{-1}(n) = \sum_{d|n} f(d) f^{-1}(\frac{n}{d}) = \varepsilon(n) = 0\)

我們可以得到 \(\displaystyle f(1)*f^{-1}(n) = \varepsilon(n) - \sum_{d|n, d \ne 1} f(d) f^{-1}(\frac{n}{d}) = - \sum_{d|n, d \ne 1} f(d) f^{-1}(\frac{n}{d})\)

移項得 \(\displaystyle f^{-1}(n) = -\frac{1}{f(1)}\sum_{d|n, d \ne 1} f(d) f^{-1}(\frac{n}{d})\)

性質七、一個積性函數的反函數仍為積性函數

根據狄利克雷卷積得到的結論

一、\(\varepsilon = \mu * 1 \Rightarrow \displaystyle \varepsilon(n) = \sum_{d|n} \mu(d) = [n=1]\)

證明:

假設 \(n\) 有 \(k\) 個不同的質因數，則我們可以根據二項式定理得到

\[\sum_{d|n} \mu(d) = \binom{k}{0}-\binom{k}{1} + \cdots + (-1)^k\binom{k}{k} = (1+(-1))^k\] 而此式只有在 \(k=0\) 時，得到\(\displaystyle \sum_{d|n} \mu(d) = 1\)，其他時候皆為0

二、\(\sigma_0 = \text{1}*\text{1}\)

顯然，一個數字 \(n\) 的因數數量為 \(\displaystyle\sigma_0(n) = \sum_{d|n} 1(d) = \sum_{d|n} 1\)

三、\(\sigma_1 = \text{Id} * \text{1}\)

顯然，一個數字 \(n\) 的因數總和為 \(\displaystyle\sigma_0(n) = \sum_{d|n} \text{Id}(d) = \sum_{d|n} d\)

四、\(\varphi = \mu * \text{Id}\)

證明:

已知 \(\displaystyle \varphi(n) = \sum_{i=1}^n [gcd(i,n)=1]\)

我們可以由將 \([gcd(i,n)=1]\) 換成與其等價的 \(\varepsilon(gcd(i,n))\)

又因為 \(\varepsilon = \mu * 1\)，我們可以將原式寫為

\(\displaystyle \varphi(n) = \sum_{i=1}^n \sum_{d|gcd(i,n)} \mu(d) = \sum_{i=1}^n \sum_{d|n} [d|i]\mu(d) = \sum_{d|n} \mu(d) \sum_{i=1}^n [d|i] = \sum_{d|n} \mu(d) \frac{n}{d}\)

莫比烏斯反演

若有一函數 \(\displaystyle f(n) = \sum_{d|n} g(d)\)，則 \(\displaystyle g(n) = \sum_{d|n} \mu(d) f(\frac{n}{d})\)

證明:

題目可被轉換成已知 \(f = g * 1\)，證明 \(g = f * \mu\)

已知 \(\varepsilon = \mu * 1\)，則 \(f * \mu = g * 1 * \mu = g * \varepsilon\)

而當式子出現 \([gcd(i,j)=1]\) 時，我們可以根據 \(\varepsilon = \mu * 1\)，將式子換成 \(\displaystyle \sum_{d|gcd(i,j)} \mu(d)\)

例題:

CSES 2417 - Count Coprime Pairs

題目:

給一個 \(n\) 項的陣列，請輸出陣列中有幾對互質的數對

測資範圍: \(1 \le n \le 10^5, 1 \le a_i \le 10^6\)

想法:

如果我們直接枚舉每個數字，那麼時間複雜度會是 \(O(n^2)\)，因此我們必須想到應該更好的做法

我們將 \(O(n^2)\) 的式子寫下來，得到 \(\displaystyle \sum_{i=1}^n \sum_{j=1}^n [gcd(a_i,a_j)=1]\)

而根據我們上面的結論，我們可以直接將 \([gcd(a_i,a_j)=1]\) 換成 \(\displaystyle \sum_{d|gcd(a_i,a_j)} \mu(d)\)

而原式則變為

\[\displaystyle \sum_{i=1}^n \sum_{j=1}^n \sum_{d|gcd(a_i,a_j)} \mu(d)\] \[= \displaystyle \sum_{i=1}^n \sum_{j=1}^n \sum_{d|a_i, d|a_j} \mu(d)\] \[= \displaystyle \sum_{i=1}^n \sum_{j=1}^n \sum_{d|a_i, d|a_j}[d|a_i][d|a_j] \mu(d)\]

我們可以將陣列中 \(d\) 的倍數的數量寫為 \(A(d)\)

則我們可以化簡原式為 \(\displaystyle \sum_{d=1}^n \mu(d) \binom{A(d)}{2}\)

而預處理 \(\mu(x)\) 的時間複雜度為 \(O(n)\)，

計算 \(d\) 的倍數數量時，我們可以加總所有 \(d\) 的倍數，時間複雜度為 \(\displaystyle O(n+\frac{n}{2}+\frac{n}{3}+\cdots)\)

可以根據調和級數的上界將複雜度寫為 \(O(n log n)\)

總時間複雜度為 \(O(n log n)\)