洛谷 P2424：约数和 ← 整数分块算法 + 约数

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