AC. 梦想

frank_c1

[BZOJ 2693] JZPTAB

发布于2016年03月03日 | 暂无评论 | 2,426阅读 | 莫比乌斯反演

题目描述

计算\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)=dg_2(d) = d^2 \mu(d)的狄利克雷卷积,由于g_1g_2均为积性函数,故g为积性函数,可以线性筛。

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