专栏文章

浅谈数论分块

vvvautedSN第一魔怔人
算法·理论参与者 45已保存评论 62

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
62 条
当前快照
1 份
快照标识符
@mhz5s1m4
此快照首次捕获于
2025/11/15 01:55
4 个月前
此快照最后确认于
2025/11/29 05:25
3 个月前
查看原文
问题引入
求 ∑i=1n⌊ni⌋\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor，其中 nn 为常数。
为了方便我们的研究，我使用绘图软件画出了 f(x)=7x(1≤x≤7)f(x) =\frac{7}{x}(1\leq x\leq 7) 的图像，也就是一种反比例函数的图像。
oS3MKP.png
因为求的值是向下取整的，显然函数 f(x)f(x) 在 [1,7][1,7] 区间内是单调递减的，我们不妨把 ⌊ni⌋\lfloor \frac n i\rfloor 取值相同的段取出来
oStJcd.png
图像被分割为了 77 个大块，但取值范围包含整数的只有 44 个，那么如果我们可以把这些包含整数的块取出来，一次性得出一个块的答案，把整块对答案的贡献加上即可。
实现：
如果要实现整块一起统计，我们需要求出每一块的块头 ll 和块尾 rr，则：
∑i=1n⌊ni⌋=∑(l,r)(r−l+1)⌊nl⌋\sum_{i=1}^n \lfloor \frac n i \rfloor = \sum _{(l,r)} (r-l+1) \lfloor \frac n l \rfloor
给出一个结论： 对于整数 ii，其所在块的右端点为 ⌊n⌊ni⌋⌋\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor，在此给出两种证明方式：
  1. 代数法
首先我们要证明 ⌊n⌊ni⌋⌋\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor 与 ii 在同一块，也就是：
⌊n⌊n⌊ni⌋⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor= \lfloor\frac{n}{i}\rfloor
易证：
⌊x⌋≤x \lfloor x\rfloor \leq x
x≤y→⌊x⌋≤⌊y⌋x \le y\to \lfloor x\rfloor \le \lfloor y\rfloor
x≥y→⌊x⌋≥⌊y⌋x \ge y\to \lfloor x\rfloor \ge \lfloor y\rfloor
则：
⌊n⌊n⌊ni⌋⌋⌋≥⌊nn⌊ni⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor \ge \lfloor\frac{n}{\frac{n}{\lfloor \frac n i \rfloor}}\rfloor=\lfloor\frac{n}{i}\rfloor
⌊n⌊n⌊ni⌋⌋⌋≤⌊n⌊nni⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor \le \lfloor\frac{n}{\lfloor\frac{n}{ \frac n i }\rfloor}\rfloor=\lfloor\frac{n}{i}\rfloor
所以：
⌊n⌊n⌊ni⌋⌋⌋=⌊ni⌋\lfloor\frac{n}{\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor}\rfloor= \lfloor\frac{n}{i}\rfloor
我们还要证明：
i≤⌊n⌊ni⌋⌋i \le \lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor
也就是 ⌊n⌊ni⌋⌋\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor 是这个块内最大的，即为块的右端点，这个很好证明：
⌊n⌊ni⌋⌋≥⌊nni⌋=i\lfloor\frac{n}{\lfloor \frac n i \rfloor}\rfloor\ge \lfloor\frac{n}{ \frac n i }\rfloor=i
这样我们就以代数方式证明了结论，如果看不懂还有几何的。
  1. 几何法
n⌊ni⌋\frac{n}{\lfloor \frac n i \rfloor} 的意义即为直线 y=⌊ni⌋y=\lfloor \frac n i \rfloor 与直线 y=nxy=\frac n x 的交点的横坐标，取整后就是这个交点左侧第一个整数横坐标，如图：
oi5Jne.png
l1l_1 为直线 y=⌊ni⌋y = \lfloor \frac n i \rfloor ，l2l_2 为直线 y=⌊ni⌋+1y=\lfloor \frac n i \rfloor +1，我们不妨设 l1l1 与直线 y=nxy=\frac n x 的交点为 PP，l2l_2 与直线 y=nxy=\frac n x 的交点为 QQ，则：
∀xQ<x≤xp,⌊nx⌋=⌊ni⌋\forall x_{Q} < x \le x_{p}, \lfloor\frac n x\rfloor = \lfloor\frac n i\rfloor
那么 xPx_{P} 也就是 n⌊ni⌋\frac{n}{\lfloor \frac n i \rfloor} 左侧的第一个整点 ⌊n⌊ni⌋⌋\lfloor \frac{n}{\lfloor \frac n i \rfloor}\rfloor 即为这些点里的最大整数点。
证毕。
复杂度证明：
当 x∈[1,⌊n⌋]x \in [1, \lfloor\sqrt n\rfloor] 这个区间，最多有 ⌊n⌋\lfloor\sqrt n\rfloor 种取值。
当 x∈(⌊n⌋,n]x \in (\lfloor\sqrt n\rfloor,n] 这个区间，⌊nx⌋\lfloor\frac n x\rfloor 显然只能取到 [1,⌊n⌋)[1, \lfloor\sqrt n\rfloor)这个区间，最多有 ⌊n⌋\lfloor\sqrt n\rfloor 种取值。
则至多有 2⌊n⌋2\lfloor\sqrt n\rfloor 种取值，复杂度为 O(n)O(\sqrt n)。
代码：
给出整数 nn，求 ∑i=1n⌊ni⌋\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor。
我们枚举每一段区间，那么当前区间右节点 +1+1 就是下个区间的左节点：
CPP
for(int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l)
}
练习题：
P3935 Calculating
一道比较模板的题，显然题目中的 f(x)f(x) 就是 xx 的约数个数，设 g(x)=∑i=1xf(i)g(x)=\sum_{i = 1} ^x f(i)， 那么有一个常见套路：
∑i=lrf(i)=g(r)−g(l−1)\sum_{i=l}^r f(i)=g(r) - g(l-1)
那么我们推一下 g(x)g(x)：
g(x)=∑i=1xf(i)=∑i=1x∑k=1x[i∣k]=∑i=1x⌊xi⌋g(x)=\sum_{i = 1} ^x f(i)=\sum_{i = 1} ^x \sum_{k = 1} ^x [i\mid k]=\sum_{i=1}^x\lfloor\frac x i\rfloor
大致的意思就是枚举一下 i∈[1,x]i\in[1,x]，看 ii 在 [1,x][1,x] 中是多少个数的约数，然后加起来就好了，这里有个结论：
∑i=1n[x∣i]=⌊nx⌋\sum_{i=1}^n[x \mid i] =\lfloor\frac n x\rfloor
然后这个 g(l−1)g(l - 1) 和 g(r)g(r) 分别整除分块推一下就好，复杂度 O(n)O(\sqrt n)
代码：
CPP
#include <stdio.h>
#define ll long long
#define mod 998244353

ll get(ll x) {
	ll ans = 0;
	
	for(ll l = 1, r; l <= x; l = r + 1) {
		r = x / (x / l);
		ans = (ans + (r - l + 1) * (x / l)) % mod;
	}
	
	return ans;
}


int main() {
	ll l, r; scanf("%lld%lld", &l, &r);
	return printf("%lld", (get(r) - get(l - 1) + mod) % mod), 0;
}
P2261 [CQOI2007]余数求和
简单推下式子：
G(n,k)=∑i=1nk mod i=∑i=1n(k−i⌊ki⌋)=nk−∑i=1ni⌊ki⌋=nk−∑(l,r)(∑i=lri)⌊kl⌋=nk−∑(l,r)(r−l+1)(l+r)2⌊kl⌋\begin{aligned} G(n,k)&=\sum_{i=1}^n k\bmod i \\ &=\sum_{i=1}^n ( k- i\lfloor\frac k i\rfloor) \\ &=nk - \sum_{i=1}^{n} i\lfloor\frac k i\rfloor \\ &=nk-\sum_{(l,r)} (\sum_{i=l}^r i)\lfloor\frac k l\rfloor \\ &=nk-\sum_{(l,r)} \frac {(r - l + 1)(l + r)} 2 \lfloor\frac k l\rfloor \end{aligned}
这里代码中有个细节，就是 l>kl>k 时 ⌊kl⌋=0\lfloor\frac k l\rfloor=0，那么 ⌊k⌊kl⌋⌋=inf⁡\lfloor \frac k{\lfloor\frac k l\rfloor}\rfloor = \inf 会爆炸，特判一下即可。
代码：
CPP
#include <stdio.h>
#define ll long long

ll min(ll a, ll b) { return a < b ? a : b; }

int main() {
	ll n, k, res = 0; scanf("%lld%lld", &n, &k);
	for(ll l = 1, r; l <= n; l = r + 1) {
		r = k / l ? min(n, k / (k / l)) : n;  
		res += (k / l) * (r - l + 1) * (l + r) / 2; 
	}
	return printf("%lld", n * k - res), 0;
}
AT2300 [ARC068C] Snuke Line
这道题不是那么板了，当 dd 取 xx 时，[l,r][l,r] 能取到的必要条件是：
l≤xp≤rl\leq xp\leq r
其中 pp 是任意正整数，推一下得到：
⌊lx⌋≤p≤⌊rx⌋\lfloor\frac l x\rfloor \leq p\leq\lfloor\frac r x\rfloor ⌊l−1x⌋<p≤⌊rx⌋\lfloor\frac {l-1} x\rfloor < p\leq\lfloor\frac r x\rfloor
若存在 pp，则一定满足：
⌊l−1x⌋<⌊rx⌋\lfloor\frac {l-1} x\rfloor < \lfloor\frac r x\rfloor
那么我们只需要求 l,rl,r 能满足的 dd 即可。
如果暴力枚举一个 dd 显然会超时，我们考虑二维数论分块，即使每一个块内的数除两个数结果都是一定的。
怎么实现的呢？如果我们求出来对于第一个数 xx 的右端点是 r1r_1，对于第二个数 yy 的右端点是 r2r_2，那么我们 rr 取 min⁡(r1,r2)\min(r_1,r_2) 即可使块内除两个数结果都使一定的。
如果当前块 aa 满足我们求出来的条件（⌊l−1x⌋<p≤⌊rx⌋\lfloor\frac {l-1} x\rfloor < p\leq\lfloor\frac r x\rfloor），那么这一段对 d∈[la,ra]d \in [l_a,r_a] 都有贡献，我们差分一下即可。
在此处还需加上一个剪枝，当 l<la≤rl < l_a\leq r 时， ⌊lla⌋=0<⌊rla⌋\lfloor\frac l {l_a}\rfloor = 0< \lfloor\frac r {l_a}\rfloor，这一段一定都满足。
代码：
CPP
#include <stdio.h>
#define Maxm 1000005

int min(int a, int b) { return a < b ? a : b; }
int d[Maxm];

int main() {
	int n, m, x, y; scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; ++ i) {
		scanf("%d%d", &x, &y); x --;
		
		for(int l = 1, r; l <= x; l = r + 1) {
			r = min(x / (x / l), y / (y / l));
			if(((x - 1) / l) < (y / l)) d[l] ++, d[r + 1] --; 
		}
		
		d[x + 1] ++, d[y + 1] --;
	}
	
	for(int i = 1, p = 0, ans = 0; i <= m; ++ i) {
		ans += d[i];
		printf("%d\n", ans);	
	}
	
}

评论

共 62 条评论，欢迎与作者交流。

正在加载评论...