题目描述

求

$$\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})$。

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