1040 最大公约数之和
给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15
输入
1个数N(N <= 10^9)
输出
公约数之和
输入样例
6
输出样例
15
题解
\]
暴力搞就行了。
1188 最大公约数之和 V2
给出一个数N，输出小于等于N的所有数，两两之间的最大公约数之和。
相当于计算这段程序（程序中的gcd(i,j)表示i与j的最大公约数）：
G=0
for i=1 to N
for j=i+1 to N
G+=gcd(i,j)
输入
第1行：1个数T，表示后面用作输入测试的数的数量。(1 <= T <= 50000)
第2 - T + 1行：每行一个数N。(2 <= N <= 5000000)
输出
共T行，输出最大公约数之和。
输入样例
3
10
100
200000
输出样例
67
13015
143295493160
1237 最大公约数之和 V3
给出一个数N，输出小于等于N的所有数，两两之间的最大公约数之和。
相当于计算这段程序（程序中的gcd(i,j)表示i与j的最大公约数）：
由于结果很大，输出Mod 1000000007的结果。
G=0
for i=1 to N
for j=1 to N
G = (G + gcd(i,j)) mod 1000000007;
输入
输入一个数N。(2 <= N <= 10^10)
输出
输出G Mod 1000000007的结果。
输入样例
100
输出样例
31080
可以看出来，T2，T3转化一下就只有数据范围不同。
题解
=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}[\gcd(i,j)=1]\\
=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}\sum_{d'|\gcd(i,j)}\mu(d)\\
=\sum_{d=1}^nd\sum_{d'=1}^{\lfloor\frac nd\rfloor}\mu(d')\lfloor\frac n{dd'}\rfloor^2
\]
整除分块两次，区别在于第二次。
- V2可以直接线性筛求出\(\mu\)前缀和。
- V3必须使用杜教筛，让\(\mu * I\)即可。
1363 最小公倍数之和
1.5 秒 131,072.0 KB 160 分 6 级题
给出一个n，求1-n这n个数，同n的最小公倍数的和。
例如：n = 6，1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30,6，加在一起 = 66。
由于结果很大，输出Mod 1000000007的结果。
输入
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 50000)
第2 - T + 1行：T个数A[i](A[i] <= 10^9)
输出
共T行，输出对应的最小公倍数之和
输入样例
3
5
6
9
输出样例
55
66
279
这题跟[SPOJ LCMsum](https://www.cnblogs.com/autoint/p/9892650.html)是一样的，只不过数据范围不一样，所以推到后面的操作不一样。
## [Star_Feel](https://www.cnblogs.com/Never-mind/p/9882196.html)的题解
原题相当于求$\sum_{i=1}^{n}\frac{i*n}{gcd(i,n)}$
先枚举\(d=\gcd(i,n)\)，然后化简得到
\]
相当于求\(1\)到\(n-1\)中，与\(n\)互质的数和，设\(y<x\)，如果\(\gcd(y,x)=1\)，那么\(\gcd(x-y,x)=1\)，两式的贡献就是\(x\)了
所以\(1\)到\(n-1\)中，与\(n\)互质的数和为\(\frac{\phi(n)*n}{2}\)，特殊的，如果\(n=1,2\)，则和为\(1\)
那么原式就等于
\]
再化简得到
\]
这样，这个式子就变成\(O(\sqrt{n})\)，但是多组数据仍会超时
实际上我们将\(n\)质因数分解得到\(n=\prod_{i=1}^{x}p[i]^a[i]\)
因为\(p[i]\)两两互质，所以可以转化为
\]
根据欧拉函数的性质可以得到
\]
再根据等比数列求和公式得到
=n+\prod_{i=1}^{x}1+\frac{p[i]^{2*a[i]+1}-p[i]}{p[i]+1}
\]
然后线筛素数加速质因数分解就可以过了，记得最后处理\(1,2\)的情况
1190 最小公倍数之和 V2
给出2个数a, b，求LCM(a,b) + LCM(a+1,b) + .. + LCM(b,b)。
例如：a = 1, b = 6，1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30,6，加在一起 = 66。
由于结果可能很大，输出Mod 10^9 + 7的结果。（测试数据为随机数据，没有构造特别坑人的Test）
输入
第1行：一个数T，表示后面用作输入测试的数的数量。(1 <= T <= 50000)
第2 - T + 1行：每行2个数a, b，中间用空格分隔(1 <= a <= b <= 10^9)
输出
共T行，输出对应的最小公倍数之和Mod 10^9 + 7的结果。
输入样例
3
1 6
10 15
41 90
输出样例
66
675
139860
Cold_Chair的题解
= b*\sum_{d | b} \sum_{i = \lfloor{ {a} \over {d}}\rfloor}^{\lceil{ {b} \over {d}}\rceil} i * [\gcd(i, { {b} \over {d}}) = 1] \\
= b*\sum_{d | b} \sum_{i = \lfloor{ {a} \over {d}}\rfloor}^{\lceil{ {b} \over {d}}\rceil} i * \sum_{d' | \gcd(i, { {b} \over {d}})} μ(d') \\
= b*\sum_{d | b} \sum_{d' | { {b} \over {d}}} μ(d') * d' * \sum_{i = \lfloor{ {b} \over {d }}\rfloor}^{\lceil{ {a} \over {d}}\rceil}i*[d' | i] \\
= b*\sum_{d | b} \sum_{d' | { {b} \over {d}}} μ(d') * d' * \sum_{i = \lfloor{ {b} \over {d*d' }}\rfloor}^{\lceil{ {a} \over {d * d'}}\rceil}i \\
= b*\sum_{d | b} \sum_{d' | { {b} \over {d}}} μ(d') * d' * (\lfloor{ {b} \over {d*d' }}\rfloor - \lceil{ {a} \over {d * d'}}\rceil + 1) * (\lfloor{ {b} \over {d*d' }}\rfloor + \lceil{ {a} \over {d * d'}}\rceil) / 2
\]
设$T = d * d’ $
\]
我们观察一下$\sum_{d | T} μ(d) * d \(
狄利克雷卷积做了这么多，轻松可得:
若\)T = \prod{p_i^{q_i}}$,那么
\]
1238 最小公倍数之和 V3
出一个数N，输出小于等于N的所有数，两两之间的最小公倍数之和。
相当于计算这段程序（程序中的lcm(i,j)表示i与j的最小公倍数）：
由于结果很大，输出Mod 1000000007的结果。
G=0
for i=1 to N
for j=1 to N
G = (G + lcm(i,j)) mod 1000000007;
输入
输入一个数N。(2 <= N <= 10^10)
输出
输出G Mod 1000000007的结果。
输入样例
4
输出样例
72
题解
=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}ij[\gcd(i,j)=1]\\
=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}ij\sum_{d'|\gcd(i,j)}\mu(d)\\
=\sum_{d=1}^nd\sum_{d'=1}^{\lfloor\frac nd\rfloor}\mu(d')(d')^2\left(\sum_{i=1}^{\lfloor\frac n{dd'}\rfloor}i\right)^2
\]
然后就变成了LG3768 简单的数学题，外面多套了一个整除分块，不过不影响复杂度。（毒瘤）