艺术分割题解

思路

设

[ P(m)=\sum_{i=1}^{m}\varphi(i), ]

其中 (\varphi) 是欧拉函数。固定最大公约数 (d)。把一对数同时除以 (d) 后，右端最大为 (\lfloor r/d\rfloor)。在所有 (1\le a\le b\le m) 中，(\gcd(a,b)=1) 的对数正好是 (\sum_{b=1}^{m}\varphi(b)=P(m))。因此

[ c(l,r)=\sum_{d=l}^{r}P\left(\left\lfloor\frac rd\right\rfloor\right). \tag{1} ]

令 (dp_g(r)) 表示把 ([1,r]) 分成 (g) 个非空连续段的最小代价，则

[ dp_g(r)=\min_{0\le j<r} \left{dp_{g-1}(j)+c(j+1,r)\right}. \tag{2} ]

每个整数 (i) 对应的对角对 ((i,i)) 必然恰好计入一个区间，所以答案至少为 (n)。若 (2^k>n)，可以让各段长度依次不超过此前所有长度之和加一，使每段 ([l,r]) 都满足 (r<2l)。此时段内只有对角对满足最大公约数至少为 (l)， 总代价恰为 (n)。因此满分算法只需计算 (k\le 16) 的状态。

做法

子任务 1：枚举分割

直接枚举 (k-1) 个切点。每个区间的 (c(l,r)) 用最大公约数定义直接计算， 取所有分割方案的最小值。

这是一条独立的精确算法，可用于核验小规模数据。

子任务 2：二次动态规划

先筛出欧拉函数与前缀和 (P)。对每个右端点 (r) 从右向左计算：

[ c(l,r)=c(l+1,r)+P(\lfloor r/l\rfloor). ]

得到全部区间代价后，直接按式 (2) 枚举断点。由于只有 (O(\log n)) 个可能非平凡的分段层数，复杂度足以通过 (n\le 450)。

子任务 3：决策单调分治

代价函数 (c(l,r)) 满足四边形不等式。等价地，在式 (2) 中，如果 (r) 从小到大变化，最优断点不会向左移动。于是每一层 DP 可以使用 分治优化：计算中点时只枚举由父递归传下来的最优断点区间，并把本次最优位置 分别作为左右子区间的边界。

对固定的 (r)，当候选断点从 (j) 移到 (j-1) 时，新段代价只增加

[ P\left(\left\lfloor\frac rj\right\rfloor\right). ]

所以一次分治节点中的候选扫描可以常数时间更新代价。递归节点首次需要的 (c(l,r)) 用整除分块按式 (1) 在 (O(\sqrt n)) 内取得。整层总复杂度为 (O(n\log n))，共 (O(\log n)) 层。

最后，对于 (2^k>n) 的询问直接输出 (n)，其余询问返回预处理的 DP 值。

正确性证明

首先，由最大公约数的唯一性，把所有合法数对按其最大公约数 (d) 分类。 当 (d\ge l) 时，除以 (d) 后得到一对不超过 (\lfloor r/d\rfloor) 的互质正整数；以较大数为 (b) 的互质对恰有 (\varphi(b)) 个。因此式 (1) 精确计算了 (c(l,r))。

其次，任意把 ([1,r]) 分成 (g) 段的方案都有唯一的最后断点 (j)。 前 (g-1) 段的最优代价为 (dp_{g-1}(j))，最后一段代价为 (c(j+1,r))。枚举所有 (j) 即得到式 (2)，故 DP 状态与转移正确。

由代价函数的四边形不等式可知转移矩阵是 Monge 矩阵，因此相邻右端点的最优 断点单调不减。分治算法只缩小到仍含真实最优断点的区间，不会漏掉最优转移， 所以计算结果与完整枚举式 (2) 相同。

最后，每个 ((i,i)) 必然产生一次贡献，答案不小于 (n)。当 (2^k>n) 时，上述倍增长度构造使每段均满足 (r<2l)，每段代价等于段长， 总代价为 (n)。上下界相同，直接输出 (n) 正确。

综上，算法对每组询问都输出 (f(n,k))。

复杂度

• 子任务 1：区间暴力预处理 (O(n^4))，分割枚举 (O!\left(\binom{n-1}{k-1}n\right))，空间 (O(n^2))。
• 子任务 2：时间 (O(n^2\log n))，空间 (O(n^2))。
• 子任务 3：预处理时间 (O(n\log^2 n))，空间 (O(n\log n))； 每组询问 (O(1))。