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
题解
\[ \sum_{i=1}^n\gcd(i,n)=\sum_{d|n}d\varphi(n) \]
暴力搞就行了.
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_{i=1}^n\sum_{j=1}^n\gcd(i,j)\=\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 个数 Ai
输出
共 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)\), 然后化简得到
\[ n*\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i[\gcd(i,\frac{n}{d})=1] \]
相当于求 \(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\)
那么原式就等于
\[ n*\sum_{d|n 且 d 不为 n}\frac{\frac{n}{d}*\phi(\frac{n}{d})}{2}+1 \]
再化简得到
\[ n+\frac{n}{2}\sum_{d|n 且 d>1}d*phi(d) \]
这样, 这个式子就变成 \(O(\sqrt{n})\), 但是多组数据仍会超时
实际上我们将 \(n\)质因数分解得到 \(n=\prod_{i=1}^{x}p[i]^a[i]\)
因为 \(p[i]\)两两互质, 所以可以转化为
\[ n+\prod_{i=1}^{x}\sum_{j=0}^{a[i]}\phi(p[i]^j)*p[i]^j \]
根据欧拉函数的性质可以得到
\[ n+\prod_{i=1}^{x}1+\sum_{j=1}^{a[i]}(p[i]-1)*p[i]^{2j-1} \]
再根据等比数列求和公式得到
\[ n+\prod_{i=1}^{x}1+(p[i]-1)*\frac{p[i]^{2*a[i]+1}-p[i]}{p[i]^2-1}\=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 的题解
\[ ans = \sum_{i = a}^b \textrm{lcm}(i) \= 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' $
\[ = b*\sum_{T | b}(\lfloor{ {b} \over {T}}\rfloor - \lceil{ {a} \over {T}}\rceil + 1) * (\lfloor{ {b} \over {T}}\rfloor + \lceil{ {a} \over {T}}\rceil) / 2 * \sum_{d | T} μ(d) * d \]
我们观察一下 $\sum_{d | T} μ(d) * d $
狄利克雷卷积做了这么多, 轻松可得:
若 \(T = \prod{p_i^{q_i}}\), 那么
\[ \sum_{d | T} μ(d) * d = \prod{1-p_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_{i=1}^n\sum_{j=1}^n\textrm{lcm}(i,j)=\sum_{i=1}^n\sum_{j=1}^n\frac{ij}{\gcd(i,j)}\=\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 简单的数学题 https://www.cnblogs.com/autoint/p/11104227.html , 外面多套了一个整除分块, 不过不影响复杂度.(毒瘤)
来源: http://www.bubuko.com/infodetail-3107170.html