数论分块 | DDOSvoid's Blog

简介

大概就是跟 $\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor$ 这种东西有关吧

取整的性质

对于 $x,y \in Z$，$x\le \lfloor \frac{n}{y} \rfloor\Leftrightarrow y\le\lfloor \frac{n}{x} \rfloor$

证明：$x\le\lfloor \frac{n}{y} \rfloor\Leftrightarrow x\le \frac{n}{y} \Leftrightarrow y\le\frac{n}{x}\Leftrightarrow y\le \lfloor \frac{n}{x} \rfloor$
对于$n,a,b\in Z$，$\lceil\frac{\lceil\frac{n}{a}\rceil}{b}\rceil=\lceil\frac{n}{ab}\rceil$，$\lfloor\frac{\lfloor\frac{n}{a}\rfloor}{b}\rfloor=\lfloor\frac{n}{ab}\rfloor$
设 $f(x)$ 是任意连续、严格单调递增函数且具有性质：当 $f(x)$ 为整数的时候，自变量 $x$ 也为整数

那么一定有 $\lfloor f(x)\rfloor = \lfloor f(\lfloor x\rfloor)\rfloor$，上取整同理
设 $n,k$ 为正整数，则有

$n=\sum_{i=0}^{k-1}\lfloor\frac{n+i}{k}\rfloor$，上取整的式子相同
设 $n$ 为正整数，$k$ 为实数，则有

$\lfloor kn\rfloor=\sum_{i=0}^{n-1}\lfloor k+\frac{i}{n} \rfloor$

如何找出值相等的一段区间

不妨假设现在的左端点是 $l$，我们要找到右端点 $r$，为了方便我们令 $k=\lfloor\frac{n}{l}\rfloor$

那么我们有 $\lfloor\frac{n}{r}\rfloor=k$，我们尝试换一下式子

$\lfloor\frac{n}{r}\rfloor=k\Leftrightarrow k\le\frac{n}{r}\Leftrightarrow r\le \frac{n}{k}\Leftrightarrow r\le\lfloor\frac{n}{k}\rfloor$ 能够发现这个上界是紧的

所以 $\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor$ 就这么求

ll ans = 0; 
for (ll l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l); 
}

另外向上取整和向下取整本质是一样的

ll ans = 0; 
for (ll l = 1, r; l <= n; l = r + 1) {
    ll t = (n + l - 1) / l;
    r = t == 1 ? n : (n - 1) / (t - 1);
    ans += (r - l + 1) * t; 
}

另外求 $\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor$ 有一种常数很小的做法

ll solve(int n){ 
	ll ans = 0; int m = sqrt(n);
    for (int i = 1; i <= m; ++i) ans += n / i;
    return ans * 2 - m * m; 
}

应用

对于 $\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor$ 这个式子，我们可以做一些简单的变形

$\sum_{i=1}^n \lfloor\frac{m}{i}\rfloor$ 这个东西也是一样的求法
$\sum_{i=1}^n f(i)\lfloor\frac{n}{i}\rfloor$ 这个东西只需要额外维护一个前缀和
$\sum_{i=1}^n\prod_{j=1}^m\lfloor\frac{a_j}{i}\rfloor$ 这个东西我们只需要在每次求右端点时，将每个数的取 $min$，需要注意这样做的复杂度为 $O(m\sqrt n)$

例题
计算 $f(n,k)=\sum_{i=1}^n \lceil\log_2i\rceil\cdot f(\lfloor\frac{n}{i}\rfloor,k-1)$

中国计量大学现代科技学院第四届“中竞杯”程序设计校赛 E.数论只会 for 循环
反过来算数论分块 Uoj #21【UR-1】缩进优化
简要题意：给定 $m$ 个区间 $[l_i,r_i]$，现在有 $n$ 个人，每个人都从 $0$ 出发，第 $i$ 个人每次只能走 $i$，即他经过的位置都是 $i$ 的倍数，求每个人经过的位置属于多少种区间

$n\le 3\times 10^5,m\le 10^5$

我们考虑对于一个人 $x$，他经过的位置属于区间 $[l_i,r_i]$ 当前仅当 $\lfloor\frac{l-1}{x}\rfloor<\lfloor\frac{r}{x}\rfloor$，我们考虑直接数论分块 $x$，每次比较两者的值做区间加即可

时间复杂度 $O(m\sqrt n)$

AT2300 [ARC068C] Snuke Line
简要题意：给定一个长度为 $n$ 的序列 $a_i$，每次操作可以选择序列中的一个数 $x$，将其变成 $a$ 和 $b$，注意 $a,b$ 插入到原序列 $x$ 的位置，且满足 $a+b=x$，我们定义 $f(l,r)$ 为最少需要多少次操作可以使得序列 $a_l,a_{l+1},\cdots,a_r$ 单调不降，求 $\sum_{i=1}^n\sum_{j=i}^nf(i,j)$

$n,a_i\le 10^5$

简要题解：我们首先能够发现两个性质，将 $v$ 分成恰好 $x$ 个数，最小值最大为 $\lfloor\frac{v}{x}\rfloor$；将 $v$ 分成若干个数，满足最大值小于等于 $x$ 且个数最小以及最小值最大，那么会分成 $\lceil\frac{v}{x}\rceil$ 个数，且最小值最大为 $\lfloor\frac{v}{\lceil\frac{v}{x}\rceil}\rfloor$

同时我们发现对于一个序列，最后一个数一定不变，那么答案是固定的，所以我们考虑 $dp$，$f_{i,j}$ 表示从 $n$ 到 $i$，$a_i$ 分解后最小值最大为 $j$ 的答案，同时我们需要另一个数组 $g_{i,j}$ 来记录方案数，注意到第二维只有 $O(\sqrt n)$ 的大小，所以我们直接暴力 $dp$ 即可，本题空间限制略微严格，需要将 $dp$ 数组滚动一下

CF 1603C Extreme Extension

简介

取整的性质

如何找出值相等的一段区间

应用

例题