CF1731E Graph Cost

给定一个初始为空的无向图，包含 $n$ 个节点，编号为 $1$ 到 $n$（即 $n$ 个节点，$0$ 条边）。你需要向图中添加 $m$ 条边，要求图中不能出现自环或重边。 如果添加一条连接节点 $u$ 和 $v$ 的边，则该边的权值必须等于 $u$ 和 $v$ 的最大公约数，即 $\gcd(u, v)$。 为了向图中添加边，你可以重复执行以下操作任意次（也可以不执行）： - 选择一个整数 $k \ge 1$； - 向图中添加恰好 $k$ 条权值为 $k+1$ 的边。添加这 $k$ 条边的总代价为 $k+1$。 注意，不能添加自环或重边。如果无法添加 $k$ 条权值为 $k+1$ 的边，则不能选择该 $k$。例如，如果你还能向图中添加 $5$ 条权值为 $6$ 的边，则可以选择 $k=5$，总代价为 $6$。但如果只能添加 $4$ 条权值为 $6$ 的边，则不能选择 $k=5$。 给定两个整数 $n$ 和 $m$，请你计算，使用上述操作构造一个包含 $n$ 个节点、恰好 $m$ 条边的图，所需的最小总代价。如果无法构造出这样的图，输出 $-1$。 注意，最终的图可以包含多个连通分量。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^6$；$1 \leq m \leq \frac{n(n-1)}{2}$）。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出构造该图所需的最小总代价。如果无法构造，输出 $-1$。

在第一个测试用例中，可以在节点 $2$ 和 $4$ 之间添加一条边，$\gcd = 2$。这是唯一可以添加的一条边，总代价为 $2$。 在第二个测试用例中，无法添加 $10$ 条边，因此答案为 $-1$。 在第三个测试用例中，可以添加如下边： - $k=1$：在节点 $2$ 和 $4$ 之间添加一条权值为 $2$ 的边（$\gcd(2, 4) = 2$），代价为 $2$； - $k=1$：在节点 $4$ 和 $6$ 之间添加一条权值为 $2$ 的边（$\gcd(4, 6) = 2$），代价为 $2$； - $k=2$：添加两条权值为 $3$ 的边：$(3, 6)$ 和 $(3, 9)$（$\gcd(3, 6) = \gcd(3, 9) = 3$），代价为 $3$。 最终共添加 $1+1+2=4$ 条边，总代价为 $2+2+3=7$，这是最小可能总代价。 由 ChatGPT 4.1 翻译