BZOJ2956 - 模积和

$$\sum_{i=1}^{n} \sum_{j=1}^{m} (n \% i) \times (m \% j) \ \ \ (i \not= j)$$

$$= (\sum_{i=1}^{n} n \% i) \times (\sum_{j=1}^{m} m \% j) - \sum_{i=1}^{\min(n, m)} (n \% i) \times (m \% j)$$

可以转化成 $A \times B - C$ 的形式,分别来求。

其中求 $A$ 和 $B$ 的方式是一样的,可以数论分块,也可以直接打表找规律。鉴于这部分不难,笔者写了后者,而描述起来而笔者又非常懒因此忽略求 $A$ 、 $B$ 直接讲求 $C$ 。当然你也可以通过推 $C$ 的方式自己推一下 $A$ 、 $B$ 。

$$C = \sum_{i=1}^{\min(n, m)} (n \% i) \times (m \% i)$$

$$= \sum_{i=1} ^ {\min(n, m)} (n - i \times \lfloor \frac {n} {i} \rfloor) \times (m - i \times \lfloor \frac {m} {i} \rfloor )$$

$$= \sum_{i=1} ^ {\min(n, m)} n \times m - m \times i \times \lfloor \frac {n} {i} \rfloor - n \times i \times \lfloor \frac {m} {i} \rfloor + i ^ 2 \times \lfloor \frac {m} {i} \rfloor \lfloor \frac {m} {i} \rfloor $$

数论分块即可。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×