zcmimi's blog

arrow_back杜教筛共3篇文章

avatar
zcmimi
2020-03-15 17:10:00

前置知识: 狄利克雷卷积

求积性函数f的前缀和:

S(n)=\sum_{i=1}^nf(i)

大部分题目都是可以线性筛的,可是某些丧心病狂的出题人会: n\le 10^{12}!

这时候需要用杜教筛了

我们构造另

avatar
zc
2020-03-18 02:07:00
查看原题

点击跳转

前置知识:

  1. 杜教筛(包括狄利克雷卷积)

  2. 数论分块

  3. 欧拉函数 或 莫比乌斯函数

(会杜教筛的大佬上述都会吧)

欧拉函数卷积推导

\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j)

根据 \sum\limits_{i|n}\varphi(n)=n (1 * \varphi = Id)

= \sum_{i=1}^n\sum_{j=1}^n ij \sum_{k|i,k|j} \varphi(k)

调换枚举顺序

= \sum_{k=1}^n \varphi(k) \sum_{k|i,k|j} ij \\ = \sum_{k=1}^n \varphi(k) \sum_{k|i}i \sum_{k|j}j \\ = \sum_{k=1}^n \varphi(k) (\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}ki)^2 \\ = \sum_{k=1}^n \varphi(k) k^2(\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}i)^2

莫比乌斯函数推导

\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j) \\ =\sum_{d=1}^n d \sum_{i=1}^n\sum_{j=1}^n ij [gcd(i,j)=d] \\ =\sum_{d=1}^n d^3 \sum_{i=1}^{\left \lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left \lfloor\frac nd\right\rfloor} ij [gcd(i,j)=1] \\ =\sum_{d=1}^n d^3 \sum_{i=1}^{\left \lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left \lfloor\frac nd\right\rfloor} ij \sum_{k|i,k|j}\mu(k) \\ =\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k) \sum_{k|i,k|j} ij \\ =\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k) k^2(\sum_{k|i}i)^2

为了方便,设sum(T)=\sum_{i=1}^T i

=\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k)k^2sum(\left \lfloor \frac n{dk}\right \rfloor)^2

T=dk

=\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 \sum_{d|T}d^3 \frac{T^2}{d^2}\mu(\frac Td) \\ =\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 T^2\sum_{d|T}d\mu(\frac Td)

其中: \sum_{d|T}d\mu(\frac Td)=\varphi(T)(\mu * Id = \varphi)

=\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 T^2 \varphi(T)

上述两种方法推导出的最终结果是一样的

接下来:

\sum_{k=1}^n \varphi(k)用杜教筛求出前缀和

k^2(\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}i)^2可以用数论分块求解

avatar
zc
2020-03-17 17:16:00
查看原题

点击跳转

1/1
Search
search