洛谷 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

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

相关推荐

3个关键指标，帮你选出专业的种子包装袋厂家

GitHub开源实测｜OpenLogi：Rust零遥测罗技外设替代工具架构深度评测与企业落地风控指南

Credit Network Modeling and Analysis via Large Language Models

更多资讯

git reset --hard 后悔药：用 reflog 和 fsck 找回丢失的代码

计算机专业生涯规划书：从Word文档到可验证技能路线图

Swift运算符速查清单：基础、位运算与自定义运算符全解析（Swift编程语言中文版）

OpenBCI脑电数据导入MNE：从CSV到脑地形图全流程

2026年AI编程工具全景：33款主流工具分类与实战选型指南

工业相机镜头选型全解析：从焦距计算到现场踩坑避雷指南

今日更新

AReaL 调试指南：从 Agent Workflow 验证到分布式训练死锁诊断

MATLAB实现GPS L1 C/A信号仿真与二维捕获验证

彻底搞懂ASCII、Unicode与UTF-8：从乱码根源到编码实战

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？