数论分块
数论分块可以快速计算一些含有除法向下取整的和式(即形如
它主要利用了富比尼定理(Fubini's theorem),将
富比尼定理
又称「算两次」,以意大利数学家圭多·富比尼(Guido Fubini)命名。 富比尼定理的积分形式:只要二重积分
例如这里的双曲线下整点的图片:
图中共分为了
引理 1
略证:
关于证明最后的小方块
QED 是拉丁词组「Quod Erat Demonstrandum」(这就是所要证明的)的缩写,代表证明完毕。现在的 QED 符号通常是
引理 2
略证:
对于
对于
综上,得证
数论分块结论
对于常数
成立且满足
证明
令
过程
数论分块的过程大概如下:考虑和式
那么由于我们可以知道
利用上述结论,我们先求出
伪代码如下:
最终得到的
参考实现
#include <iostream>
long long H(int n) {
long long res = 0; // 储存结果
int l = 1, r; // 块左端点与右端点
while (l <= n) {
r = n / (n / l); // 计算当前块的右端点
// 累加这一块的贡献到结果中。乘上 1LL 防止溢出
res += 1LL * (r - l + 1) * (n / l);
l = r + 1; // 左端点移到下一块
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t, n;
std::cin >> t;
while (t--) {
std::cin >> n;
std::cout << H(n) << '\n';
}
return 0;
}
N 维数论分块
求含有
一般我们用的较多的是二维形式,此时可将代码中 r = n / (n / i)
替换成 r = min(n / (n / i), m / (m / i))
。
向上取整的数论分块
向上取整与前文所述的向下取整十分类似,但略有区别:
对于常数
成立且满足
注意
当
证明
例题:CF1954E Chain Reaction
题意:有一排
思路
下面是一种使用二维数论分块的解法:
使用积木大赛的技巧,令
对于相邻的两个怪兽,使用二维数论分块,分段求出它们对一段
复杂度
实现
#include <algorithm>
#include <iostream>
constexpr int N = 100009;
int n, a[N], maxn;
long long ans[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
maxn = std::max(maxn, a[i]);
}
for (int i = 0; i < n; ++i)
for (int l = 1, r;; l = r + 1) {
r = std::min(l < a[i] ? (a[i] - 1) / ((a[i] - 1) / l) : N,
l < a[i + 1] ? (a[i + 1] - 1) / ((a[i + 1] - 1) / l)
: N); // 二维数论分块
if (r == N) break;
int x = (a[i + 1] - 1) / l - std::max(a[i] - 1, 0) / l;
if (x > 0) ans[l] += x, ans[r + 1] -= x; // 累加贡献
}
++ans[0]; // ⌈a/l⌉=(a-1)/l+1的式子当a=0时不成立,需要修正
for (int i = 1; i <= maxn; ++i)
std::cout << (ans[i] += ans[i - 1]) << " \n"[i == maxn];
return 0;
}
习题
-
CQOI2007 余数求和(需要一点转化和特判)
-
UVa11526 H(n)(几乎可以当做模板题)
-
POI2007 ZAP-Queries(数论分块一般配合 莫比乌斯反演 用以进一步降低复杂度;本题需要用到
这一条莫反结论)
创建日期: September 11, 2021