LOJ 2193 – 「SDOI2014」数表

题目链接:LOJ 2193

题目给出$T$组询问,每组询问格式为$(n, m, a)$,回答:

$$ \sum_{i = 1}^{n} \sum_{j = 1}^{m} f({\rm gcd}(i,j))  \bmod 2^{31}$$

其中:

$$ f(x) = \sigma(x) [\sigma(x) \leq a] $$

推公式:

$$ \begin{aligned} & \sum_{i = 1}^{n} \sum_{j = 1}^{m} f({\rm gcd}(i,j)) \\  = & \sum_{d = 1}^{\min(n,m)} f(d) \sum_{i = 1}^{n} \sum_{j = 1}^{m} [{\rm gcd}(i,j) = d]  \\ = & \sum_{d = 1}^{\min(n,m)} f(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [{\rm gcd}(i,j) = 1] \\ = & \sum_{d = 1}^{\min(n,m)} f(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \sum_{t | {\rm gcd}(i,j)} \mu(t) \\ = & \sum_{d = 1}^{\min(n,m)} f(d)  \sum_{t = 1}^{\lfloor \frac{\min(n,m)}{d} \rfloor} \mu(t) \lfloor \frac{n}{td} \rfloor \lfloor \frac{m}{td} \rfloor  \end{aligned} $$

令 $td = u$,交换求和次序,得到上式等于

$$ \sum_{u = 1}^{\min(n,m)} (f * \mu)(u) \lfloor \frac{n}{u} \rfloor \lfloor \frac{m}{u} \rfloor $$

首先我们要预处理除$\sigma(n)$和$\mu(n)$,线性筛即可。

然后考虑$f(i)$能影响到所有的$(f*\mu)(i \times t)$,所以我们只要对$f$的值域进行排序,再对询问进行排序,每次把符合要求的点计算贡献,用线段树或者树状数组动态维护前缀和,整除分块计算答案,离线回答。

时间复杂度$\Theta (n \log n + T \log T + T \sqrt{n})$。

 

说点什么

avatar
50
  Subscribe  
提醒