题目描述

计算$\sum_{i=1}^{n} \sum_{j=1}^{m} {lcm (i,j)} \mod (10^8 + 9)$，有多组数据。

输入格式

一个正整数T表示数据组数。

接下来T行 每行两个正整数 表示N、M。（T <= 10000；N, M<=10000000）

输出格式

共T行，每行一个整数 表示第i组数据的结果。

题目解析

膜拜神犇PoPoQQQ。

将最小公倍数转化为我们熟悉的最大公约数，有

$$ans = \sum_{i=1}^{n} \sum_{j=1}^{m} {\frac{ij}{\gcd (i,j)}}$$

设$F(n,m)=\sum_{i=1}^{n} \sum_{j=1}^{m} {ij [\gcd(i,j) == 1]}$，则有

$$ans = \sum_{d=1}^{\min(n,m)} {\frac{d^2 F(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor)}{d}} = \sum_{d=1}^{\min(n,m)}{d \times F(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor)}$$

那怎样高效地求出$F(n,m)$呢？

令$G(n,m) = \sum_{i=1}^{n} \sum_{j=1}^{m} {ij} = \frac{n(n+1)} {2} \frac{m(m+1)} {2}$，可得

$$\begin{aligned} F(n,m) &= \sum_{i=1}^{n} \sum_{j=1}^{m} ij[\gcd(i,j) == 1] \\ &= \sum_{i=1}^{n} \sum_{j=1}^{m} ij \sum_{d|\gcd(i,j)} {\mu(d)} \\ &= \sum_{i=1}^{n} \sum_{j=1}^{m} ij \sum_{d|i \&\& d|j} {\mu(d)} \\ &= \sum_{d=1}^{\min(n,m)} {\mu(d) \sum_{d|i}^{n} \sum_{d|j}^{m} {ij}} \\ &= \sum_{d=1}^{\min(n,m)} {\mu(d) d ^ 2 \sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor} {ij}} \\ &= \sum_{d=1}^{\min(n,m)} {d ^ 2 \mu(d) G(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor)} \end{aligned}$$

我们只需求出$h(n) = n^2 \mu(n)$的前缀和，即可在单次$O(\sqrt{n})$的复杂度下求出$F$函数，于是总复杂度是$O(n)$。

至此，我们已经可以解决本题的弱化版[BZOJ 2154] Crash的数字表格。但本题有多组数据，我们尝试将复杂度优化到单次询问$O(\sqrt{n})$。我们把$F$函数在原式展开：

$$\begin{aligned} ans &= \sum_{d=1}^{\min(n,m)}{d \sum_{i=1}^{\min(n,m)}{i^2 \mu(i)G(\left \lfloor \frac{n}{id} \right \rfloor,\left \lfloor \frac{m}{id} \right \rfloor)}} \\ &= \sum_{T=1}^{\min(n,m)} {G(\left \lfloor \frac{n}{T} \right \rfloor,\left \lfloor \frac{m}{T} \right \rfloor) \sum_{d|T}{\frac{T}{d} d^2 \mu(d)}} \end{aligned}$$

于是我们只需要求出$g(n) = \sum_{d|n} {\frac{n} {d} d ^ 2 \mu(d)}$的前缀和即可在$O(\sqrt{n})$解决问题。我们来分析这个函数，可以发现$g(n)$是$g_1(d)=d$和$g_2(d) = d^2 \mu(d)$的狄利克雷卷积，由于$g_1$和$g_2$均为积性函数，故$g$为积性函数，可以线性筛。

最终的总复杂度为$O(T\sqrt{n})$。