Luogu P1829 - Crash 的数字表格

题面

给定 n,mn, m,试求:

i=1nj=1mlcm(i,j)\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j)

答案对 2010100920101009 取模。

数据范围

1n,m1071 \le n,m \le 10^7

题目链接

分析

显然我们需要往莫比乌斯函数的方向考虑。因此,我们要把 lcm(i,j)\operatorname{lcm}(i, j) 换作使用 gcd(i,j)\gcd(i, j) 表示。

为了方便,下文中假设 nmn \le m(如果 n>mn > m 那么两者交换一下就好了)。

i=1nj=1mlcm(i,j)=i=1nj=1mijgcd(i,j)\begin{aligned}
\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \frac{ij}{\gcd(i, j)}
\end{aligned}

我们发现 gcd(i,j)\gcd(i, j) 位于分母,这十分不好处理。因此我们在这里介绍一个技巧,令 gcd(i,j)=k\gcd(i, j) =k 并枚举 kk 从而使得 gcd(i,j)\gcd(i, j) 离开分母:

i=1nj=1mlcm(i,j)=i=1nj=1mk=1nijk[gcd(i.j)=k]=k=1min(n,m)i=1nkj=1mkijk[gcd(i,j)=1]\begin{aligned}
\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sum\limits_{k = 1}^{n} \frac{ij}{k} [\gcd(i. j) = k] \
= & \sum\limits_{k = 1}^{\min(n, m)} \sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} ijk[\gcd(i, j) = 1]
\end{aligned}

终于出现了我们最喜闻乐见的 [gcd(i,j)=1][\gcd(i, j) = 1]。我们可以依据我上一篇文章 浅谈莫比乌斯反演 应用一节中提到的方法对其进行变换:

i=1nj=1mlcm(i,j)=k=1ni=1nkj=1mkijkdgcd(i,j)μ(d)=k=1ni=1nkj=1mkijkd=1nkμ(d)[dgcd(i,j)]=k=1nkd=1nkμ(d)i=1nkj=1mkij[dgcd(i,j)]=k=1nkd=1nkμ(d)i=1nkdj=1mkdijd2[1gcd(i,j)]=k=1nkd=1nkμ(d)d2i=1nkdij=1mkdj\begin{aligned}
\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{k = 1}^{n} \sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} ijk \sum\limits_{d \mid \gcd(i, j)} \mu(d) \
= & \sum\limits_{k = 1}^{n} \sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} ijk \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) [d \mid \gcd(i, j)] \
= & \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) \sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} ij [d \mid \gcd(i, j)] \
= & \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) \sum\limits_{i = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{kd} \right\rfloor} ijd^2 [1 \mid \gcd(i, j)] \
= & \sum\limits_{k = 1}^{n}k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) d^2 \sum\limits_{i = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor}i \sum\limits_{j = 1}^{\left\lfloor \frac{m}{kd} \right\rfloor} j
\end{aligned}

我们注意到最后两项实际上都是等差数列求和。我们不妨令 g(i)=i=1nig(i) = \sum\limits_{i = 1}^{n} i,那么有:

i=1nj=1mlcm(i,j)=k=1nkd=1nkμ(d)d2g(nkd)g(mkd)\begin{aligned}
\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{k = 1}^{n}k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) d^2 g\left( \left\lfloor \frac{n}{kd} \right\rfloor \right) g\left( \left\lfloor \frac{m}{kd} \right\rfloor \right) \
\end{aligned}

T=kdT = kd,同时我们考虑枚举 TT,则有:

i=1nj=1mlcm(i,j)=k=1nkd=1nkμ(d)d2g(nT)g(mT)=T=1ng(nT)g(mT)dTμ(d)d2Td=T=1ng(nT)g(mT)TdTdμ(d)\begin{aligned}
\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i, j) = & \sum\limits_{k = 1}^{n}k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d) d^2 g\left( \left\lfloor \frac{n}{T} \right\rfloor \right) g\left( \left\lfloor \frac{m}{T} \right\rfloor \right) \
= & \sum\limits_{T = 1}^{n} g\left( \left\lfloor \frac{n}{T} \right\rfloor \right) g\left( \left\lfloor \frac{m}{T} \right\rfloor \right) \sum\limits_{d \mid T}\mu(d)d^2\frac{T}{d} \
= & \sum\limits_{T = 1}^{n} g\left( \left\lfloor \frac{n}{T} \right\rfloor \right) g\left( \left\lfloor \frac{m}{T} \right\rfloor \right)T \sum\limits_{d \mid T}d\mu(d)
\end{aligned}

不妨令 F(n)=dndμ(d)F(n) = \sum\limits_{d \mid n} d\mu(d) 并对 F(n)F(n) 进行研究。

我们发现,当 aba \perp b 时(当 a,ba, b 互质时):

F(a)=dadμ(d)F(b)=dbdμ(d)\begin{aligned}
F(a) = & \sum\limits_{d \mid a} d\mu(d) \
F(b) = & \sum\limits_{d \mid b} d\mu(d) \
\end{aligned}

我们不难发现,由 aba \perp b,故 aabb 不存在公共因子,因此 ia, jbijabi \mid a, \ j \mid b \Leftrightarrow ij \mid ab。又由于 μ(n)\mu(n) 本身又是积性函数,所以有 μ(ab)=μ(a)μ(b)\mu(ab) = \mu(a) \cdot \mu(b)。由此:

F(a)F(b)=iaiμ(i)jbjμ(j)=ijabijμ(ij)=kabkμ(k)=F(ab)\begin{aligned}
F(a) \cdot F(b) = & \sum\limits_{i \mid a}i\mu(i)\sum\limits_{j \mid b}j\mu(j) \
= & \sum\limits_{ij \mid ab}ij \cdot \mu(ij) \
= & \sum\limits_{k \mid ab}k\mu(k) \
= & F(ab)
\end{aligned}

我们发现 F(n)F(n) 也是个积性函数!既然是积性函数…… 那么一定可以线性筛:

  1. F(1)=1F(1) = 1
  2. aa 是质数,F(a)=1aF(a) = 1 - a
  3. aba \perp bF(ab)=F(a)F(b)F(ab) = F(a) \cdot F(b)

由此一来,我们就可以 O(N)\mathcal{O}(N) 初始化(线性筛 F(n)F(n)),并借助整除分块 O(N)\mathcal{O}(\sqrt{N}) 解决询问了。

实现

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/11/21/luogu-p1829/