题面
今天的数学课上，$\text{Crash}$小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数$a$和$b$，$lcm(a, b)$表示能同时整除$a$和$b$的最小正整数。例如，$lcm(6, 8) = 24$。
回到家后，Crash还在想着课上学的东西，为了研究最小公倍数，他画了一张$N×M$的表格。每个格子里写了一个数字，其中第$i$行第$j$列的那个格子里写着数为$lcm(i, j)$。一个$4×5$的表格如下：
1 | 1 2 3 4 5 |
看着这个表格，Crash想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题：这个表格中所有数的和是多少。当$N$和$M$很大时，Crash就束手无策了，因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大，Crash只想知道表格里所有数的和 $mod\;20101009$ 的值。
题解
简化题意：
给定$n$,$m$
求 $\sum_{i=1}^n \sum_{j=1}^n lcm(i, j)$
以下的一切都默认$n<m$
我们都知道$lcm(i,j)=\frac{ij}{gcd(i,j)}$
所以所求化简
$$
\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}
$$
看到$gcd(i,j)$很不爽，于是就再提出来
$$
\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m[gcd(i, j)==d]\frac{ij}{d}
$$
也就是
$$
\sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i, j)==1]ijd
$$
把$d$提出来
$$
ans=\sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i, j)==1]ij
$$
前面这一堆看起来管不了了
看后面的一段
$$
\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i, j)==1]ij
$$
看到$\frac{n}{d}$这种东西很不爽呀
就写成这样吧。。
$$
\sum_{i=1}^{x}\sum_{j=1}^{y}[gcd(i, j)==1]ij
$$
这种东西怎么求？
令
$$
f(d)=\sum_{i=1}^{x}\sum_{j=1}^{y}[gcd(i, j)==d]ij
$$
根据莫比乌斯反演的常见套路
设
$$
g(d)=\sum_{i=1}^x\sum_{j=1}^y[d|gcd(i, j)]ij
$$
直接把$d$提出来
$$
g(d)=d^2\sum_{i=1}^{\frac{x}{d}}\sum_{j=1}^{\frac{y}{d}}[1|gcd(i, j)]ij
$$
$1|gcd(i, j)$是显然成立的
所以
$$
g(d)=d^2\sum_{i=1}^{\frac{x}{d}}\sum_{j=1}^{\frac{y}{d}}ij
$$
这玩意明显可以$O(1)$求（相当于两个等差数列相乘）
所以，要求的东西就是
$$f(1)=\sum_{i=1}^xμ(i)g(i)$$
这道题就解决了一大半了
现在我们的复杂度是$O(n\sqrt{n})$与$O(n^2)$之间
需要继续优化
很显然的
$$
ans=\sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i, j)==1]ij
$$
这个式子可以数论分块一波，复杂度少了$O(\sqrt{n})$
还不够
继续看，
$$
f(1)=\sum_{i=1}^xμ(i)g(i)
$$
这个式子把$g(x)$展开
$$
f(1)=\sum_{i=1}^xμ(i)i^2\sum_{p=1}^{\frac{x}{i}}\sum_{q=1}^{\frac{y}{j}}pq
$$
还是可以数论分块
但是要预处理$μ(i)∗i^2$的前缀和
然后复杂度就成了$O(n)$啦
代码
1 | #include<bits/stdc++.h> |