求助数学题

题目总版

sc_iwe @ 2024-11-18 19:51:22

求

\sum_{i=1}^n \sum_{j=1}^n lcm(i, j)

时间限制:0.1s 空间：512MB [link](https://www.luogu.com.cn/problem/U499096) 自己出的题不会做了（我好蒻....）

by sc_iwe @ 2024-11-18 19:51:42

lcm是最小公倍数

by kaixinguo @ 2024-11-18 19:55:07

或许是递推预处理 \gcd，然后求出来 \text{lcm} 求和？时间复杂度 \mathcal{O}(n^2)

by Ether13 @ 2024-11-18 19:56:25

这不莫反基础题？

by zhouyuhang @ 2024-11-18 19:56:25

https://www.luogu.com.cn/problem/P1829

by xUwT @ 2024-11-18 19:59:14

你这个数据是怎么样的

by xUwT @ 2024-11-18 20:00:12

数论分块好啊

by yangryan @ 2024-11-18 20:04:36

https://www.luogu.com.cn/problem/P5435

by luuia @ 2024-11-18 20:09:14

把 \operatorname{lcm}(i,j) 换成 \dfrac{i\times j}{\gcd(i,j)} 然后正常莫反就行了，数据范围应该能开到 10^7

by sc_iwe @ 2024-11-20 11:59:30

谢谢各位神犇，关注了

by World_Ender @ 2024-11-21 08:40:02

[BOF:TT]

| 下一页