洛谷 P2424：约数和 ← 整数分块算法 + 约数
【题目来源】
https://www.luogu.com.cn/problem/P2424
【题目描述】
对于一个数 X，函数 f(X) 表示 X 所有约数的和。例如：f(6)=1+2+3+6=12。对于一个 X，Smart 可以很快的算出 f(X)。现在的问题是，给定两个正整数 X,Y(X<Y)，Smart 希望尽快地算出 f(X)+f(X+1)+……+f(Y)的值，你能帮助 Smart 算出这个值吗？
【输入格式】
输入文件仅一行，两个正整数 X 和 Y(X<Y)，表示需要计算 f(X)+f(X+1)+⋯+f(Y)。
【输出格式】
输出只有一行，为 f(X)+f(X+1)+⋯+f(Y) 的值。
【输入样例】
123 321
【输出样例】
72543
【数据范围】
对于 20% 的数据有 1≤X<Y≤10^5。
对于 60% 的数据有 1≤X<Y≤1×10^7。
对于 100% 的数据有 1≤X<Y≤2×10^9。
【算法分析】
● 洛谷 P2424 要求计算：∑f(i)，i=1~n。其中，f(i) 表示 i 的所有约数之和。直接计算每个数的约数之和再累加，复杂度太高。我们用交换求和顺序的技巧：
（1）枚举每个可能的约数 d，统计它在 1∼n 中作为约数出现的次数。
（2）对于约数 d，它在 1∼n 中作为约数出现的次数是 ⌊n/d⌋，每次贡献 d。因此：∑f(i)=d⋅⌊n/d⌋，d=1~n。
例如：若 i=1~6，则 ∑f(i)=f(1)+f(2)+f(3)+f(4)+f(5)+f(6)=1+(1+2)+(1+3)+(1+2+4)+(1+5)+(1+2+3+6)
=1×⌊6/1⌋+2×⌊6/2⌋+3×⌊6/3⌋+4×⌊6/4⌋+5×⌊6/5⌋+6×⌊6/6⌋。
● 对于块 [le,ri]，⌊n/d⌋=k 为常数，需要计算：∑d⋅k=k⋅∑d，d=le~ri。区间 [le,ri] 内所有 d 的和是一个等差数列：∑d=(le+ri)⋅(ri−le+1)/2，d=le~ri。
● 注意：这道题交换了求和顺序，从“枚举每个数 i，求它的所有约数之和”变成了“枚举每个约数 d，统计它在多少个数中出现过”。这个转换改变了枚举的对象（从 i 变成了 d），但 d 本身的顺序依然是 1, 2, 3, ... 递增的，没有被打乱。
● 本题代码与“洛谷 P3935：Calculating：https://blog.csdn.net/hnjzsyjyj/article/details/162990202”及其类似。
【算法代码】
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL cal(LL n) { LL t=0; for(LL le=1,ri=0; le<=n; le=ri+1) { LL k=n/le; ri=n/k; t=t+k*(ri+le)*(ri-le+1)/2; } return t; } int main() { ios::sync_with_stdio(0); cin.tie(0); LL le,ri; cin>>le>>ri; LL ans=cal(ri)-cal(le-1); cout<<ans<<"\n"; return 0; } /* in:123 321 out:72543 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/162990202
https://blog.csdn.net/hnjzsyjyj/article/details/163011369
https://blog.csdn.net/hnjzsyjyj/article/details/162819219