数论分块
数论分块可以快速计算一些含有除法向下取整的和式(即形如
它主要利用了富比尼定理(Fubini's theorem),将
富比尼定理
又称「算两次」,以意大利数学家圭多·富比尼(Guido Fubini)命名。 富比尼定理的积分形式:只要二重积分
例如这里的双曲线下整点的图片:
图中共分为了
引理 1
略证:
关于证明最后的小方块
QED 是拉丁词组「Quod Erat Demonstrandum」(这就是所要证明的)的缩写,代表证明完毕。现在的 QED 符号通常是
引理 2
略证:
对于
对于
综上,得证
数论分块结论
对于常数
成立的最大的满足
证明
令
过程
数论分块的过程大概如下:考虑和式
那么由于我们可以知道
利用上述结论,我们先求出
伪代码如下:
最终得到的
参考实现
1 2 3 4 5 6 7 8 9 10 11 |
|
N 维数论分块
求含有
一般我们用的较多的是二维形式,此时可将代码中 r = n / (n / i)
替换成 r = min(n / (n / i), m / (m / i))
。
习题
CQOI2007 余数求和(需要一点转化和特判)
UVa11526 H(n)(几乎可以当做模板题)
POI2007 ZAP-Queries(数论分块一般配合 莫比乌斯反演 用以进一步降低复杂度;本题需要用到
这一条莫反结论)
本页面最近更新:2024/4/19 19:35:31,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:2044-space-elevator, 383494, 99-woods, Backl1ght, CCXXXI, Great-designer, iamtwz, ksyx, Marcythm, qwqAutomaton, sshwy, StudyingFather, tder6, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用