首页 > 题解 > bzoj 4407 于神之怒加强版

bzoj 4407 于神之怒加强版

Description

给下N,M,K.求

Input

输入有多组数据,输入数据的第一行两个正整数T,K,代表有T组数据,K的意义如上所示,下面第二行到第T+1行,每行为两个正整数N,M,其意义如上式所示。

Output

如题

Sample Input

1 2

3 3

Sample Output

20

HINT

1<=N,M,K<=5000000,1<=T<=2000

题解

$$
\large
\begin{aligned}
&\;\;\;\;\; \sum_{i = 1}^n\sum_{j = 1}^m (i,j)^k \\
&= \sum_d d^k \sum_{i = 1}^n\sum_{j = 1}^m [(i,j)=b] \\
&= \sum_d d^k \sum_{i = 1}^{n \over d}\sum_{j = 1}^{m \over d}[(i,j)=1] \\
&= \sum_d d^k \sum_{i = 1}^{n \over d}\sum_{j = 1}^{m \over d}\sum_{p|(i,j)} \mu(p) \\
&= \sum_d d^k \sum_p \mu(p) {n\over dp} {m\over dp} \\
&= \sum_d d^k \sum_p \mu(p) {n\over T} {m\over T} \\
&= \sum_{T = 1}^{min(n,m)} {n\over T} {m\over T} \sum_{d|T}d^k \mu({T\over d})
\end{aligned}
$$

$$f(T)=\sum_{d|T}d^k\mu({T\over d})$$

这个式子是个狄利克雷卷积的形式,因为两个函数都是积性函数,卷起来也是积性函数。

这样就可以用线筛直接搞了


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×