LOJ 2185 – 「SDOI2015」约数个数和

题目链接:LOJ 2185

这题需要用到一个套路性结论:$d(i \times j) = \sum_{x|i} \sum_{y|j} [{\rm gcd}(x,y) = 1]$,暂时还没有搞懂证明方法,待填坑。

有了这个式子之后就可以愉快地推公式了。

$$ \begin{aligned}  & \sum_{i = 1}^{n} \sum_{j = 1}^{m} d(i \times j) \\ = & \sum_{i = 1}^{n} \sum_{j = 1}^{m} \sum_{x | i} \sum_{y | j} [{\rm gcd}(x,y) = 1] \\ = & \sum_{x = 1}^{n} \sum_{y = 1}^{m} \sum_{x | i}^{1 \leq i \leq n} \sum_{y | j}^{1 \leq i \leq m} [{\rm gcd}(i, j) = 1] \\ = & \sum_{x = 1}^{n} \sum_{y = 1}^{m} [{\rm gcd}(i, j) = 1] \sum_{x | i}^{1 \leq i \leq n} \sum_{y | j}^{1 \leq i \leq m} 1 \\ = &  \sum_{x = 1}^{n} \sum_{y = 1}^{m} \sum_{d | {\rm gcd}(x,y) } \mu(d) \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor \\ = & \sum_{d = 1}^{\min \{ n, m\} } \mu (d) \sum_{d | x}^{1 \leq x \leq n} \sum_{d | y}^{1 \leq y \leq m} \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor \\ = & \sum_{d = 1}^{\min \{ n, m\} } \mu (d) \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor } \sum_{y = 1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{dx} \rfloor \lfloor \frac{m}{dy} \rfloor \\ = & \sum_{d = 1}^{\min \{ n, m \} } \mu (d) \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{\lfloor \frac{n}{d} \rfloor}{x} \rfloor \sum_{y = 1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{\lfloor \frac{m}{d} \rfloor}{y} \rfloor \end{aligned} $$

记函数$f(u) = \sum_{i = 1}^{u} \lfloor \frac{u}{i} \rfloor$,则答案为

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

化简到这里,如果能在短时间内求出$f(u)$,那么这个问题就解决了:预处理莫比乌斯函数前缀和,然后整除分块。

下面的问题是如何处理$f(u)$。这里要用到一个结论

$$ \sum_{i = 1}^{n} d(i) = \sum_{i = 1}^{n} \lfloor \frac{n}{i} \rfloor  $$

证明如下:

$$ \begin{aligned} & \sum_{i = 1}^{n} d(i) =  \sum_{i = 1}^{n} \sum_{d | i} 1 =  \sum_{d = 1}^{n} \lfloor \frac{n}{d} \rfloor \end{aligned} $$

这里是对这个性质的逆用。到这里,只需要预处理出$d(i)$的前缀和即可$O(1)$算出$f(u)$的值。这里的$n \leq 5 \times 10 ^ 4$,直接筛$d(i)$就可以,由于$d(i)$是积性函数,也可线性筛。

 

说点什么

avatar
50
  Subscribe  
提醒