DGF & 杜教筛笔记

阿丑 · 2022-05-13 19:27:58 · 算法·理论

狄利克雷生成函数（DGF）

对于无穷序列 f，定义其狄利克雷生成函数（Dirichlet series generating function，DGF）为：
\tilde F(x)=\sum\limits_{i\ge1}\dfrac{f_i}{i^x}
如果序列 f 满足积性：\forall i\bot j,\ f_{ij}=f_if_j，那么其 DGF 可以由质数幂处的取值表示：
\tilde F(x)=\prod\limits_{p\in\mathcal P}\left(1+\frac{f_p}{p^x}+\frac{f_{p^2}}{p^{2x}}+\frac{f_{p^3}}{p^{3x}}+\cdots\right)
对于两个序列 f,g，其 DGF 之积对应的是两者的狄利克雷卷积序列的 DGF：
\tilde F(x)\tilde G(x)=\sum\limits_i\sum\limits_j\dfrac{f_ig_j}{(ij)^x}=\sum\limits_i\frac1{i^x}\sum\limits_{d\mid i}f_dg_{\frac id}

——OI wiki

常见积性函数的 DGF：

名称	符号	DGF
单位函数	\varepsilon(n)=[n=1]	1
/	1(n)=1	\zeta(x)=\sum\limits_{i\ge1}\frac 1{i^x}
莫比乌斯函数	\mu(n)	\operatorname{\tilde M(x)}=\frac1{\zeta(x)}
欧拉函数	\varphi(n)	\tilde\Phi(x)=\frac{\zeta(x-1)}{\zeta(x)}
幂函数	I_k(n)=n^k	\tilde I_k(x)=\zeta(x-k)
约数幂函数	\sigma_k(n)=\sum\limits_{d\mid n}d^k	\tilde \Sigma_k(x)=\zeta(x-k)\zeta(x)
无平方因子数	u(n)=\mid\mu(n)\mid	\tilde U(x)=\frac{\zeta(x)}{\zeta(2x)}

其中 \zeta(x) 为黎曼函数。由积性性质有 \zeta(x)=\prod\limits_{p\in\mathcal P}\dfrac1{1-p^{-x}}。

常见等式：

\varepsilon=1*\mu

I=1*\varphi

结论：

积性函数的狄利克雷卷积仍是积性函数。

积性函数的逆元也是积性函数。

杜教筛

用于解决数论函数前缀和问题。

有：

\sum_{i=1}^n(f*g)(i)=\sum_{i=1}^ng(i)\sum_{j=1}^{\left\lfloor\frac ni\right\rfloor}f(j)

若求 f 的前缀和，而能构造 g 使得 g 与 f*g 的前缀和较好求（以能 O(1) 求为例），则可以通过上式来求 f 的前缀和：

变形，有：

\sum_{i=1}^nf(i)=\frac{\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)\sum_{j=1}^{\left\lfloor\frac ni\right\rfloor}f(j)}{g(1)}

可以递归求解 \sum_{j=1}^{\left\lfloor\frac ni\right\rfloor}f(j)。

注意到 \forall i,j,\ \lfloor\dfrac{\lfloor\frac ni\rfloor}j\rfloor=\lfloor\dfrac{\lfloor\frac nj\rfloor}i\rfloor=\lfloor\dfrac n{ij}\rfloor，故一次求解中 \sum_{j=1}^xf(j) 中的 x 只有 \mathcal O(\sqrt n) 种取值。复杂度 \mathcal O(n^\frac34)，需要记忆化。

优化，预处理 x\le m（m\ge n^\frac12）时的前缀和（以能线性预处理为例），则总复杂度为 \mathcal O(m+\dfrac n{m^\frac12})。取 m=n^\frac23，总复杂度为 \mathcal O(n^\frac23)。

以 f=\mu，g=1 为例给出代码。

void sieve() {
    for(int i=2, j, u; i<=m; ++i) {
        if(!notp[i]) pri[++cntp]=i, mu[i]=-1;
        for(j=1; (u=pri[j]*i)<=m && i%pri[j]; ++j) notp[u]=1, mu[u]=-mu[i];
        if(u<=m) notp[u]=1, mu[u]=0;
    }
    mu[1]=1;
    rep(i, 2, m) mu[i]+=mu[i-1];
}

map<int, int> smu;
int cal_mu(ui n) {
    if(n<=m) return mu[n];
    if(smu[n]) return smu[n];
    int res=1;
    for(ui l=2, r; l<=n; l=r+1) res-=((r=n/(n/l))-l+1)*cal_mu(n/l); //整除分块
    return smu[n]=res;
}

可以使用 DGF 来推导满足条件的 g。\varepsilon,1,I_k 均属于较易求出前缀和的函数。