图的代价 题解

思路

令 $d=k+1$。一次选择 $k$ 会加入 $d-1$ 条 gcd 为 $d$ 的边，代价为 $d=(d-1)+1$。因此总成本等于边数 $m$ 加上操作次数；问题转化为在各种可用的“边数包”中，凑出恰好 $m$，并最小化包的数量。

设 $E_d$ 为 gcd 恰好等于 $d$ 的无序点对数，则大小为 $d-1$ 的包最多使用 $\lfloor E_d/(d-1)\rfloor$ 次。

三个算法层级分别是：

1. $n\le20$ 时枚举点对得到 $E_d$，再做有界背包求最少包数。
2. $\sum n^2\le4\times10^6$ 时仍枚举所有点对统计 $E_d$，但利用包大小连续且单位边代价随 $d$ 下降，按 $d$ 从大到小贪心。
3. 满规模时用欧拉函数前缀快速求 $E_d$，再执行同样的贪心。

做法

把一对 gcd 为 $d$ 的点同时除以 $d$，得到 $1\le a<b\le\lfloor n/d\rfloor$ 且 $\gcd(a,b)=1$。固定较大的数 $b$ 时，较小且互质的 $a$ 有 $\varphi(b)$ 个，所以

预处理欧拉函数及其前缀和即可在 $O(1)$ 时间得到每个 $E_d$。

从最大的 $d$ 向 $2$ 扫描。大小为 $d-1$ 的包最多有 $c_d=\lfloor E_d/(d-1)\rfloor$ 个，当前还需要 $r$ 条边时取

个包，并把答案增加 $xd$。较大的包用一次能覆盖更多边，因而不可能比用更小的包需要更多操作；所有包大小从 $1$ 连续出现，剩余量最终由更小包补齐。若扫描结束仍有剩余边，则无解。

所有计数、$m$ 与答案必须使用 64 位整数。

复杂度

预处理到最大 $n$ 的欧拉函数为 $O(N\log\log N)$，每组扫描 $O(n)$，总时间 $O(N\log\log N+\sum n)$，空间 $O(N)$。