AC. 梦想

frank_c1

[BZOJ 2956] 模积和

发布于2016年06月02日 | 暂无评论 | 539阅读 | 数论

题目描述

\sum_{i=1}^{n} \sum_{j=1}^{m} {(n \mod i)(m \mod j)[i \neq j]}

输入格式

两个整数n,m

1 \le n,m \le 10 ^ 9

输出格式

一个整数表示答案\mod 19940417的值。

题目解析

我们先不考虑i = j的情况。由分配律原式可转化为

(\sum_{i=1}^{n} {n \mod i})(\sum_{i=1}^{m} {m \mod i})

我们只需考虑

\sum_{i=1}^{n} {n \mod i}

这一部分是经典问题,有

\sum_{i=1}^{n} {n \mod i} = \sum_{i=1}^{n} {n-\lfloor \frac{n} {i} \rfloor i} = n^2 - \sum_{i=1}^{n} {\lfloor \frac{n} {i} \rfloor i}

\lfloor \frac{n} {i} \rfloor只有O(\sqrt{n})种取值,分段求一下即可。

再来考虑我们i = j。这一部分的答案应从上述推导的结果中减去,有

\begin{aligned} w &= \sum_{i=1}^{\min(n,m)} {(n \mod i)(m \mod i)} \\ &= \sum_{i=1}^{min(n,m)} {(n-\lfloor \frac{n} {i} \rfloor i)(m-\lfloor \frac{m} {i} \rfloor i)} \\ &= \sum_{i=1}^{\min(n,m)} {nm - ni \lfloor \frac{m} {i} \rfloor - mi \lfloor \frac{n} {i} \rfloor + \lfloor \frac{n} {i} \rfloor \lfloor \frac{m} {i} \rfloor i^2} \\ &= nm\min(n,m) + \sum_{i=1}^{\min(n,m)} {\lfloor \frac{n} {i} \rfloor \lfloor \frac{m} {i} \rfloor i^2 - ni \lfloor \frac{m} {i} \rfloor - mi \lfloor \frac{n} {i} \rfloor} \end{aligned}

还是分段求即可。时间复杂度O(\sqrt{n})

话说公式推起来不难,写起来真麻烦,到处模模模……