\[\Huge\text{Dirichlet 字首和及其應用}
\]
全文概要
- Dirichlet 字首和定義；
- Dirichlet 字首和的算法，及其拓展；
- Mobius 函數，Mobius 反演以及它們與 Dirichlet 字首和，Dirichlet 卷積之間關系；
- 具體應用。
1 Dirichlet 字首和定義
給定數列 \(a_i\)，定義數列 \(b_i=\sum\limits_{d|i} a_d\)，即所有下标為該下标約數的原數組之和。
例子：\(n=10,a_i=\left\{1,4,6,9,2,4,5,6,4,3\right\}\)，則 \(b_i=\left\{1,5,7,14,3,15,6,20,11,10\right\}\)
2 模闆問題與複雜度
2.1 Dirichlet 字首和
模闆
2.1.1 算法說明
\(n\le 2\times 10^7\)，說明要用優于/微劣于 \(\mathcal{O}(n)\) 的算法。
對于一個數 \(a_j\)，它會被計算到 \(b_{1\times j},b_{2\times j}\dots\) 中。
而對于 \(a_k(k\ge 1,k|j)\) ，可以發現會被記入 \(b_{1\times k},b_{2\times k},b_{3\times k}\dots\)
可見 \(b_{1\times j},b_{2\times j}\dots\) 也肯定會被包含；
是以可以得到一個結論：\(b_j\) 會被 \(b_{1\times j},b_{2\times j},b_{3\times j}\dots\) 所包含。
但是如果直接計算 \(b_{4\times j}\)，會被 \(b_{j}\) 和 \(b_{2\times j}\) 同時計入，有重複；
于是稍稍變換計算方式：每次乘以一個不超過其下标本身的質數，就可以解決這個問題，也能夠保證不重複地計算。
核心代碼：
for(int i=1;i<=cnt;i++)
for(int j=1;j*pr[i]<=n;j++) a[j*pr[i]]+=a[j];
其中
cnt
是所有素數的總數，
pr[i]
為第 \(i\) 個素數。
2.1.2 算法正确性證明
下面證明上述代碼是正确的，也即不重複且不遺漏：
下證第 \(i(i\le cnt)\) 輪過後，對于滿足 \(l|d,\frac{d}{l}=pr_1^{\alpha_1}pr_2^{\alpha_2}\dots pr_i^{\alpha_i}\) 的 \(l\)，令這些 \(l\) 組成集合 \(S_{i,d}\)。\(b_d=\sum\limits_{l\in S_{i,d}} a_l\)
\(i=0\) 時，顯然成立！（\(b_i=a_i\)）
假設對 \(i=k-1\) 成立，此時 \(b_1=a_1\)，\(j=1\) 成立！
假設 \(b_1\dots b_p\) 均滿足如上結論，
\(p=j+1\) 時，如果 \(pr_i|j+1\)，那麼 \(b_{j+1}\leftarrow b_{j+1}+b_{\frac{j+1}{pr_i}}\)，即 \(b_{j+1}=\sum\limits_{l\in{S_{k-1,j+1}}}a_l+\sum\limits_{l\in{S_{k,\frac{j+1}{pr_i}}}}a_l\)
由定義可知 \(S_{k,\frac{j+1}{pr_i}}\cap S_{k-1,j+1}=\varnothing\)，且 \(S_{k,\frac{j+1}{pr_i}}\cup S_{k-1,j+1}=S_{k,j+1}\)；
是以 \(b_{j+1}=\sum\limits_{l\in{S_{k,j+1}}}a_l\)
得證！
2.1.3 舉例驗證
舉個例子直覺地驗證一下各個數字的變化情況：\(n=10,cnt=4,pr_i=\left\{2,3,5,7\right\}\)
初始情況：
a1,a2,a3,a4,a5,a6,a7,a8,a9,a10
\(i=1,pr_i=2\) 後：
a1,a2+a1,a3,a4+a2+a1,a5,a6+a3,a7,a8+a4+a2+a1,a9,a10+a5
\(i=2,pr_i=3\) 後：
a1,a2+a1,a3+a1,a4+a2+a1,a5,a6+a3+a2+a1,a7,a8+a4+a2+a1,a9+a3+a1,a10+a5
\(i=3,pr_i=5\) 後：
a1,a2+a1,a3+a1,a4+a2+a1,a5+a1,a6+a3+a2+a1,a7,a8+a4+a2+a1,a9+a3+a1,a10+a5+a2+a1
\(i=4,pr_i=7\) 後：
a1,a2+a1,a3+a1,a4+a2+a1,a5+a1,a6+a3+a2+a1,a7+a1,a8+a4+a2+a1,a9+a3+a1,a10+a5+a2+a1
2.2 Dirichlet 字尾和
類似的，給定數列 \(a_i\)，定義數列 \(b_i=\sum\limits_{i|d} a_d\)。
即所有下标為該下标倍數的原數組之和。
我們可以如下操作：每次同樣乘以一個不超過其下标本身的質數，但是由于字首變為字尾，是以把計算順序改變一下——變成從後向前計算。
為什麼呢？畫張圖。
上圖為 Dirichlet 字首和，下面的數字代表給他貢獻的 \(a\) 數組下标，上面是 \(b\) 數組下标
上圖為 Dirichlet 字尾和
for(int i=1;i<=cnt;i++)
for(int j=n/pr[i];j>=1;j--) a[j]+=a[j*pr[i]];
用類似 Dirichlet 字首和的證法也可以得證！
2.3 逆推 Dirichlet 字首和
即已知字首和 \(b_i\)，求原數組 \(a_i\)；
相當于是一個差分（Dirichlet 差分）。
是以直接按照字首和的代碼倒序周遊即可。
for(int i=cnt;i>=1;i--)
for(int j=n/pr[i];j>=1;j--) a[j*pr[i]]-=a[j];
2.4 逆推 Dirichlet 字尾和
還是 Dirichlet 差分，可以按照字尾和代碼倒序周遊。
for(int i=cnt;i>=1;i--)
for(int j=1;j*pr[i]<=n;j++) a[j]-=a[j*pr[i]];
2.5 Dirichlet 字首和及其拓展複雜度
這個算法複雜度為 \(\mathcal{O}(\sum\limits_{\text{質數p}\le n} \dfrac{n}{p})\)，與埃氏篩的複雜度相同，是以可以得知複雜度約為 \(\mathcal{O}(n\log\log n)\)
3 Dirichlet 卷積 和 Mobius 反演
3.1 Dirichlet 卷積 和 Mobius 函數之間的關系
3.1.1 什麼是Dirichlet 卷積
Dirichlet 卷積，是定義在兩個數論函數 \(f,g\) 上的 \(f*g\) 滿足 \((f*g)(n)=\sum\limits_{d|n}f(d)\times g(n/d)\)
Dirichlet 卷積滿足如下的規律：
- 交換律：\(f*g=g*f\)
- 結合律：\((f*g)*h=f*(g*h)\)
- 配置設定律：\(f*(g+h)=f*g+f*h\)
- 存在機關元：定義 \(\epsilon(n)=[n=1]\)，則 \(f*\epsilon =f\)
- 保持積性：如果 \(f,g\) 都是積性函數，那麼 \(f*g\) 也是積性函數。
3.1.2 什麼是 Mobius 函數
Mobius 函數用 \(\mu\) 來表示。
如果 \(n=1\) 則 \(\mu(n)=1\)；
如果 \(n\) 沒有平方因子，則 \(\mu(n)=(-1)^{\text{n的素因子個數}}\)；
如果 \(n\) 有平方因子，則 \(\mu(n)=0\)。
定理一：
\[\epsilon(n)=\sum\limits_{d|n}\mu(d)
即 \(\epsilon=\mu*1\)；
證明：
設 \(n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k},n'=\prod\limits_{i=1}^{k} p_i\)
是以 \(\sum\limits_{d|n} \mu(d)=\sum\limits_{d|n'}\mu(d)=\sum\limits_{i=0}^{k}C^i_k\times (-1)^k=(1+(-1))^k=[n=1]=\epsilon(n)\)
是以我們可以利用 Dirichlet 卷積處理 Mobius 函數！
3.1.3 莫比烏斯反演
如果函數 \(f,g\) 滿足
\[f(n)=\sum\limits_{d|n} g(d)
則
\[g(n)=\sum\limits_{d|n}\mu(d)f(\dfrac{n}{d})
證明：根據定義可以得到 \(f=g*1\)
兩邊同時卷上 \(\mu\)
可以得到：
\[f*\mu=g*1*\mu
\[\because 1*\mu =\epsilon
\[\therefore f* \mu=g*\epsilon=g
因為 \(\mu(p^k)=[k=1]\)，而且 \(\mu\) 是積性函數，是以可以用線性篩模闆計算。
void prime(ll n){
mu[1]=1;
for(int i=2;i<=n;i++){
if(!vst[i]) pr[++cnt]=i,mu[i]=-1;
for(ll j=1;j<=cnt&&i*pr[j]<=n;j++){
vst[i*pr[j]]=1;
if(!(i%pr[j])){mu[i*pr[j]]=0;break;}
mu[i*pr[j]]=-mu[i];
}
}
}
3.2 複雜度的分析
假設我們現在要算 \(f=g*1\)，如果對于每一個 \(f_i\) 都是暴力計算，複雜度是 \(\mathcal{O}(\sqrt n)\) 的，總和是 \(\mathcal{O}(n\sqrt n)\)；
如果預計算完了每個數的約數清單，可以得知複雜度約為 \(\mathcal{O}(n/1+n/2+\dots n/n)\)，而每個數計算也需要其約數個數的複雜度。
而 \(\lim\limits_{n\rightarrow \infty}\sum\limits_{i=1}^{n}\dfrac{n}{i}=n\ln n\)（素數定理）
是以預計算約數的複雜度總和是 \(\mathcal{O}(n\log n)\)。
而我們使用了 Dirichlet 卷積以後複雜度下降為 \(\mathcal{O}(n\log \log n)\)。
主要的差距就在于 Dirichlet 卷積以後我們省去了重新計算 \(f_d(d|i)\) 的過程。
舉個例子：在前兩種情況，計算 \(f_{10}\) 時，前兩種方法都會将 \(f_5\) 重新計算，但是事實上在 Dirichlet 卷積當中 之前計算好的 \(f_5\) 可以被重複利用，進而減少計算次數。
3.3 從多元空間看 Dirichlet 字首和
我們回過頭來看一看 \(n=10\) 時最後的 \(b_i\)：
a1,a2+a1,a3+a1,a4+a2+a1,a5+a1,a6+a3+a2+a1,a7+a1,a8+a4+a2+a1,a9+a3+a1,a10+a5+a2+a1
乍看之下似乎沒有規律。
如果我們将 \(i\) 質因數分解以後，并且以各個質因數的幂次作為坐标呢？
舉個比較形象的例子：（為了表示友善暫時隻列出前三根軸）紅色線條框出的立方體即為 \(b_{30}\) 所包含的所有 \(a_d\) 在這個空間中的坐标，而藍色框出的部分即為 \(b_{100}\) 所包含的 \(a_d\)。
如果我們要在這個空間内做差分的話，由容斥原理，令 \(n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}\) 可得
\[a_{n}=\sum\limits_{d|n,\frac{n}{d}=p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k},\beta_i\in{0,1}} (-1)^{\sum\limits_{i=1}^{n} \beta_i}\times b_d
\[\therefore a_{n}=\sum\limits_{d|n,\frac{n}{d}=p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k},\beta_i\in{0,1}} \mu\left(\dfrac{n}{d}\right)\times b_d
由 Mobius 函數的定義，如果存在平方的質數為 \(n\) 約數，\(\mu(n)=0\)。
\[\therefore a_{n}=\sum\limits_{d|n} \mu\left(\dfrac{n}{d}\right)\times b_d
\[\therefore a_{n}=\sum\limits_{d|n} \mu\left(d\right)\times b_{\frac{n}{d}}
這就是 Dirichlet 差分！
再看一下 Mobius 反演的式子：
會發現 Dirichlet 差分和 Mobius 反演本質一樣。
借此發現了 Dirichlet 字首和/差分 與 Mobius 反演之間的關系。
4 具體的應用
例題1
即求
\[\sum\limits^{n}_{x=1}\sum\limits^{m}_{y=1}[\gcd(x,y)\text{為質數}]
設 \(g(x)\) 為 \(\gcd(i,j)=x\) 的個數，\(f(x)\) 為 \(\gcd(i,j)=k\times d,k=1,2,\dots\) 的個數。（假設是單組資料）
\[\therefore g(x)=\sum\limits^{n}_{i=1}\sum\limits^{m}_{j=1}[\gcd(i,j)=d],f(x)=\sum\limits^{n}_{i=1}\sum\limits^{m}_{j=1}[\gcd(i,j)=kd]
\[f(x)=\sum\limits_{d|x} g(d)=\left\lfloor\dfrac{n}{x}\right\rfloor\left\lfloor\dfrac{m}{x}\right\rfloor
\[g(x)=\sum\limits_{x|d}\mu\left(\left\lfloor\dfrac{d}{x}\right\rfloor\right)f(x)
\[\sum\limits_{\text{p是質數}}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} [\gcd(i,j)=p]
把 \(g(p)\) 的表達式代入。
\[\sum\limits_{\text{p是質數}}g(p)
可以使用莫比烏斯反演！
\[\sum_{\text{p是質數}}\sum\limits_{p|d}\mu\left(\left\lfloor\dfrac{d}{p}\right\rfloor\right)f(d)
改變枚舉項，枚舉
\[\left\lfloor\dfrac{d}{p}\right\rfloor
\[\sum\limits_{\text{p是質數}}\sum\limits_{d=1}^{\min(\frac{n}{p},\frac{m}{p})}\mu(d)f(d\times p)=\sum\limits_{\text{p是質數}}\sum\limits_{d=1}^{\min(\frac{n}{p},\frac{m}{p})}\mu(d)\left\lfloor\dfrac{n}{d\times p}\right\rfloor\left\lfloor\dfrac{m}{d\times p}\right\rfloor
把 \(
d\times p\) 換元成
\(T\) 可以得到：
\[\sum\limits_{T=1}^{\min(n,m)}\sum\limits_\text{p|T,p是質數}\mu\left(\left\lfloor\dfrac{T}{p}\right\rfloor\right)\left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor
再交換一下 \(\sum\) 的順序：
\[\sum\limits_{T=1}^{\min(n,m)}\left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor\sum\limits_\text{p|T,p是質數}\mu\left(\left\lfloor\dfrac{T}{p}\right\rfloor\right)
是以就可以線性篩 \(\mu\) 函數，整除分塊并記錄字首和。
複雜度 \(\mathcal{O}(n+\sqrt{n})\)。