整除分块

概述

整除分块，用于快速求出形如

$$
\sum_{i=1}^{n}f(\left\lfloor\frac{n}{i} \right\rfloor)
$$

的式子。

随着 $i$ 的变化，$\left\lfloor\frac{n}{i}\right\rfloor$ 大约只有 $\sqrt{n}$ 种不同的取值，并且取值相同的数是连续的。也就是一段数满足：

$$
\left\lfloor\frac{n}{l} \right\rfloor=\left\lfloor\frac{n}{l+1} \right\rfloor=\cdots=\left\lfloor\frac{n}{r-1} \right\rfloor=\left\lfloor\frac{n}{r} \right\rfloor
$$

我们想要求出这个区间的左右端点 $l, r$，这样 $f(\left\lfloor\dfrac{n}{i} \right\rfloor), i\in[l, r]$ 就只需要算一次，再乘上 $(r-l+1)$ 即可。

注意到端点满足：$\left\lfloor\dfrac{n}{l} \right\rfloor=\left\lfloor\dfrac{n}{r} \right\rfloor=k\in \Bbb{Z}$，在此条件下，我们求 $r$ 的最大值，所以有关系：

$$
\begin{cases}
k=\left\lfloor\dfrac{n}{l} \right\rfloor\\
r=\max(i),\quad i\times k\leq n
\end{cases}
$$

因此

$$
r=\left\lfloor\dfrac{n}{k} \right\rfloor=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l} \right\rfloor} \right\rfloor
$$

于是我们知道了，对于任意 $i$ 满足 $l\leq i\leq \left\lfloor\dfrac{n}{\left\lfloor\frac{n}{l} \right\rfloor} \right\rfloor$，其 $\left\lfloor\dfrac{n}{i} \right\rfloor$ 的值都是相同的。

参考资料。

UVA11526 H(n)

求 $\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor$.

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

P2261 [CQOI2007]余数求和

题意

给定 $n, k$，求：

$$
G(n, k)=\sum_{i=1}^n{k\bmod i}
$$

题解

$$
\begin{aligned}
\operatorname{ans}&=\sum_{i=1}^{n}k\bmod i\\
&=\sum_{i=1}^{n}k-i\times \left\lfloor\frac{k}{i}\right\rfloor\\
&=n\cdot k-\sum_{i=1}^{n}i\times \left\lfloor\frac{k}{i}\right\rfloor\\
\end{aligned}
$$

减号后面用整除分块，于是在 $\mathcal{O}(\sqrt{k})$ 的时间复杂度内解决。

01分数规划

概述

描述一

每种物品有两个权值 $a, b$，可以从中选出其中一些，求 $\dfrac{\sum{a_i}}{\sum{b_i}}$ 的极值。

描述二

给定数列 $a_i$，$b_i$，找一组 $w_i\in\{0, 1\}$ 使 $\frac{\sum w_i\times a_i}{\sum w_i\times b_i}$ 最大，只需求出这个最大值。

思路

二分答案，以求最大值为例。

若 $\operatorname{mid}$ 可行，则存在一组 $w_i$ 满足：

$$
\begin{aligned}
&\frac{\sum a_i\times w_i}{\sum b_i\times w_i} > \operatorname{mid}\\
\Rightarrow &\sum a_i\times w_i-\operatorname{mid} \sum b_i\times w_i>0\\
\Rightarrow &\sum w_i(a_i-\operatorname{mid}\times b_i)>0
\end{aligned}
$$

应用见例题。

P4377 [USACO18OPEN]Talent Show G

题意

给定数列 $a_i$，$b_i$，找一组 $w_i\in{0, 1}$ 使 $\frac{\sum w_i\times a_i}{\sum w_i\times b_i}$ 最大，求出这个最大值。

同时要求 $\sum w_i\times b_i\geq W$.

$W$ 是给定常数，$n\leq 250$，$W\leq 1000$.

题解

需要在满足 $\sum w_i\times b_i\geq W$ 的条件下，求出 $[\sum w_i(a_i-\operatorname{mid}\times b_i)]_{\operatorname{max}}$.

这可以用背包解决。

P4322 [JSOI2016]最佳团体

题意

给定一棵 $n$ 个节点的树，每个点有权值 $a_i, b_i$.

选出恰好 $k$ 个点，且要求：若节点 $u$ 被选中，则 $\operatorname{Father}_u$ 也一定要被选。

求 $\dfrac{\sum a_i}{\sum b_i}$ 的最大值，$n,k\leq 2500$.

题解

需要在满足题目条件的前提下，求出 $[\sum (a_i-\operatorname{mid}\times b_i)]_{\operatorname{max}}$.

考虑树上背包，设 $f[u][j]$ 表示在 $u$ 的子树中，取出 $j$ 个节点的最大收益值。

求出 $f$ 后，只需判断 $f[\operatorname{root}][k]>0$ 是否成立。

转移方法：首先有 $f[u][0]=0$。若 $j\neq 0$，则节点 $u$ 一定被取，分别从 $u$ 的每棵子树 $v$ 进行转移。即：

$$
f[u][j] =
\left\{
\begin{array}{lr}
0 ,& j=0\\
\max\limits_{k<j}(f[u][j-k]+f[v][k]) ,& j\neq 0
\end{array}
\right.
$$

P3705 [SDOI2017]新生舞会

题意

有两个点集 $A, B$，均包含 $n$ 个元素。现在要让不同点集之间的元素两两配对。

对于每个配对 $(A_i, B_j)$，会产生两个权值 $a_{i, j}$ 和 $b_{i, j}$.

找一组配对方案，使 $\dfrac{\sum a}{\sum b}$ 最大，求出这个最大值。

$1\leq n\leq 100, 1\leq a_{i, j}, b_{i, j}\leq 10^4$.

题解

先做相同的转化。这道题中，求 $[\sum w_i(a_i-\operatorname{mid}\times b_i)]_{\operatorname{max}}$ 的方法是最大费用最大流。

建一个二分图，每条边流量均为 $1$，二分图之间连边的费用为对应的权值 $w=a_{i_j}-\operatorname{mid}\times b_{i, j}$.