狄利克雷卷積 && 杜教篩 入門 — P4213 【模板】杜教篩（Sum）
狄利克雷卷積
數論函式
數論函式是指一類函式，其定義域是正整數，值域是一個數集
積性函式都是數論函式
常見的數論函式有
- $id(n) = n$ 單位函式，完全積性函式
- $\epsilon(n) = [n = 1]$ 元函式，完全積性函式
- $d(n)$ 約數個數，積性函式
- $\sigma(n)$ 約數和函式，積性函式
- $\mu(n)$ 莫比烏斯函式，積性函式
- $\varphi(n)$ 尤拉函式，積性函式
狄利克雷卷積
定義兩個數論函式的狄利克雷卷積為 $*$:
若$t = f * g$
則
$$
t(n) = \sum_{i|n} f(n) g(\lfloor \frac{n}{i} \rfloor)
$$
在狄利克雷卷積中
- 單位元是 $\epsilon$
- 若$f * g = \epsilon$ 則我們稱 $g$ 為 $f$ 的逆元
- $f * g = g * f$
- $(f * g) * h = f * (g * h)$
- $(f + g) * h = f * h + g * h$
- $(xf) * g = x(f*g)$
一些應用
莫比烏斯反演
我們先來證明一點莫比烏斯反演裡面的東西
$$
\sum_{d|n} \mu(d) = [n = 1]
$$
很明顯，化成卷積的形式即為
$$
\mu * 1 = \epsilon
$$
然後我們來證明莫比烏斯反演
$$
g(n) = \sum_{d|n} f(d)\ \
f(n) = \sum_{d|n} \mu(d) g(\lfloor \frac{n}{d} \rfloor)
$$
顯然可以化為
$$
g = f * 1
$$
$$
\begin{aligned}
f & = \mu * g \\
& = \mu * f * 1 \\
& = f * \epsilon \\
& = f
\end{aligned}
$$
等式成立，展開後得到
$$
f(n) = \sum_{d|n} \mu(n) g(\lfloor \frac{n}{d} \rfloor)
$$
得證
尤拉函式與莫比烏斯函式
已知
$$
n = \sum_{d|n} \varphi(d)
$$
顯然
$$
\begin{aligned}
\varphi * 1 & = id\\
\varphi * 1 * \mu & = id * \mu\\
\varphi * \epsilon & = id * \mu\\
\varphi &= id*\mu
\end{aligned}
$$
展開得
$$
\varphi(n) = \sum_{d|n} \mu(d) \frac{n}{d}
$$
除於$n$得
$$
\frac {\varphi(n)}{n} = \sum_{d|n} \frac{\mu(d)}{d}
$$
(然後你可以用這個式子證明已知的公式)(證明證明證明)
杜教篩
杜教篩用於在小於線性的時間求一個積性函式得字首和
即 求 $\sum_{i=1}^n f(i)$
$f$ 為積性函式
為了愉快得求出這個式子我們需要設$h = f * g$
$h$ 和 $g$ 均為積性函式
記 $S$ 為 $f$ 字首和
然後Let's do it!
$$
\begin{aligned}
\sum_{i=1}^n
& = \sum_{i=1}^n \sum_{d|i} g(d)f(\frac{d}{i}) \\
& = \sum_{d=1}^n g(d) \sum_{i=1}^{\frac{n}{d}} f(i) \\
&=\sum_{d=1}^n g(d) S(\frac{n}{d})
\end{aligned}
$$
讓我們做一點微小的改變
顯然
$$
g(1)S(n) = \sum_{i=1}^n h(i) – \sum_{d=2}^n g(d) S(\frac{n}{d})
$$
除法分塊 + 遞迴處理
只要你$h(i)$得字首和能在大約$O(1)$左右得時間求出來（預處理後$O(1)$也可以的）時間複雜度就是$O(n^{\frac{2}{3}})$
為什麼？反正我是不會QAQ
來吧，上模板
Luogu P4213 【模板】杜教篩（Sum）
題目
莫比烏斯函式
$$
S(n) = \sum_{i=1}^n \mu(i)
$$
眾所周知$\mu * 1 = \epsilon$
$\epsilon$ 的字首和過於顯然——$1$
沒什麼說的了
尤拉函式
$$
S(n) = \sum_{i=1}^n \varphi(i)
$$
眾所周知$\varphi * 1 = id$
$id$ 的字首和…等差數列了解一下
沒什麼說的了
程式碼
#include <cstdio>
const int N = 2e6 + 10;
int T, n;
int sum_mu[N], sum_mu2[3400];
int mu[N], phi[N], pri[N], pcnt;
int has_phi[3400], has_mu[3400];
long long sum_phi[N], sum_phi2[3400];
bool vis[N];
void pre(){
vis[1] = true; mu[1] = 1; phi[1] = 1;
sum_mu[1] = sum_phi[1] = 1;
for(int i = 2; i < N; i++){
if(vis[i] == false){
pri[ ++pcnt ] = i;
mu[i] = -1;
phi[i] = i - 1;
}
for(int j = 1; j <= pcnt; j++){
int tmp = pri[j] * i;
if(tmp >= N)
break;
vis[tmp] = true;
if(i % pri[j] == 0){
mu[tmp] = 0;
phi[tmp] = phi[i] * pri[j];
break;
}
mu[tmp] = -mu[i];
phi[tmp] = phi[i] * (pri[j] - 1);
}
sum_mu[i] = sum_mu[i - 1] + mu[i];
sum_phi[i] = sum_phi[i - 1] + (long long)phi[i];
}
}
long long ask_phi(int x){
if(x < N) return sum_phi[x];
int tmp = n / x;
if(has_phi[tmp] == n)
return sum_phi2[tmp];
has_phi[tmp] = n;
long long &ans = sum_phi2[tmp];
ans = (1LL * (1LL + x) * x) / 2;
for(int left = 2, rig; left <= x; left = rig + 1){
rig = x / (x / left);
ans -= (rig - left + 1) * ask_phi(x / left);
}
return ans;
}
int ask_mu(int x){
if(x < N) return sum_mu[x];
int tmp = n / x;
if(has_mu[tmp] == n)
return sum_mu2[tmp];
has_mu[tmp] = n;
int &ans = sum_mu2[tmp];
ans = 1;
for(int left = 2, rig; left <= x; left = rig + 1){
rig = x / (x / left);
ans -= (rig - left + 1) * ask_mu(x / left);
}
return ans;
}
int main(){
#ifdef woshiluo
freopen("luogu.4213.in", "r", stdin);
freopen("luogu.4213.out", "w" ,stdout);
#endif
pre();
scanf("%d", &T);
while(T--){
scanf("%d", &n);
printf("%lld %d\n", ask_phi(n), ask_mu(n));
}
fclose(stdin);
fclose(stdout);
}