计蒜客41302 – K Sum

题目链接:ICPC 2019 南京网络赛 E

$f_n(k)$化简得:

$$ f_n(k) \begin{aligned} & = \sum_{u=1}^{n} \lfloor \frac{n}{u} \rfloor ^ k  \sum_{d|u} d^2 \mu(\frac{u}{d}) \end{aligned} $$

代入目标式并交换求和次序:

$$\begin{aligned} & \sum_{i=2}^{k} \sum_{u=1}^{n} \lfloor \frac{n}{u} \rfloor ^ k  \sum_{d|u} d^2 \mu(\frac{u}{d}) \\ =& \sum_{u=1}^{n}\sum_{i=2}^{k} \lfloor \frac{n}{u} \rfloor ^ k  \sum_{d|u} d^2 \mu(\frac{u}{d}) \\ =& \sum_{u=1}^{n} t(\lfloor \frac{n}{u} \rfloor)  ({\rm Id}^2 * \mu)(u) \end{aligned} $$

其中$t(\lfloor \frac{n}{u} \rfloor)$表示一个等比数列求和的结果,对于比较大的$k$,可以考虑欧拉函数降幂,然后可以整除分块求解。坑点是要特判公比为$1$的情况,公比为$1$的时候的$k$的计算值是$k \bmod P$而不是$k \bmod \varphi(P)$。

下面考虑求式中Direchlet卷积的前缀和。$n$的范围是$10^9$,考虑使用亚线性筛。

记$f(x) =({\rm Id}^2 * \mu)(x) $,$g(x) = 1$,则$f * g = {\rm Id}^2 * \mu * 1 = {\rm Id}^2 * \epsilon = {\rm Id}^2$,可求前缀和,考虑杜教筛。

设$F(n) = \sum_{x=1}^{n} f(x)$,则可以对$f*g$求和推得:

$$ F(n) = \frac{n(n+1)(2n+1)}{6} – \sum_{d=2}^{n} F(\lfloor \frac{n}{d} \rfloor) $$

线性筛预处理$n \leq 10^6$,然后杜教筛即可。

渐进时间复杂度$O(T (n^{\frac{2}{3}} + \sqrt{n} \times \log P) )$。

 

说点什么

avatar
50
  Subscribe  
提醒