整除分块#

概述#

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

\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);
}

cpp

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}$ .

2022省选集训 – 优化基础技巧