← 返回题目列表

Codeforces · 1731/E

E. 图形成本

中文机器翻译题面 查看原题

给您一个最初为空的无向图,其中包含 $$$n$$$ 节点,编号从 $$$1$$$ 到 $$$n$$$(即 $$$n$$$ 节点和 $$$0$$$ 边)。您想要向图中添加 $$$m$$$ 边,因此该图不会包含任何自循环或多条边。

如果添加连接两个节点 $$$u$$$ 和 $$$v$$$ 的边,则其权重必须等于 $$$u$$$ 和 $$$v$$$ 的最大公约数,i。 e. $$$\gcd(u, v)$$$。

为了向图中添加边,您可以重复以下过程任意次数(可能为零):

- 选择一个整数 $$$k \ge 1$$$;
- 将 $$$k$$$ 边精确添加到图表中,每个边的权重等于 $$$k + 1$$$。添加这些 $$$k$$$ 边总共花费 $$$k + 1$$$。

例如,如果您可以在权重 $$$6$$$ 的图表中添加 $$$5$$$ 的边,则可以添加它们,并且整包 $$$5$$$ 边的成本为 $$$6$$$。但如果您只能将权重为 $$$6$$$ 的 $$$4$$$ 边添加到图中,则无法对 $$$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$$$。

示例

输入 #1

4
4 1
6 10
9 4
10 11

输出 #1

2
-1
7
21

注意

在第一个测试用例中,我们可以在顶点 $$$2$$$ 和 $$$4$$$ 之间添加一条边,其中 $$$\gcd = 2$$$。这是添加 $$$1$$$ 优势的唯一可能方法,成本为 $$$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$$$。