Graph Cost

题目描述

You are given an initially empty undirected graph with $ n $ nodes, numbered from $ 1 $ to $ n $ (i. e. $ n $ nodes and $ 0 $ edges). You want to add $ m $ edges to the graph, so the graph won't contain any self-loop or multiple edges. If an edge connecting two nodes $ u $ and $ v $ is added, its weight must be equal to the greatest common divisor of $ u $ and $ v $ , i. e. $ \gcd(u, v) $ . In order to add edges to the graph, you can repeat the following process any number of times (possibly zero): - choose an integer $ k \ge 1 $ ; - add exactly $ k $ edges to the graph, each having a weight equal to $ k + 1 $ . Adding these $ k $ edges costs $ k + 1 $ in total. Note that you can't create self-loops or multiple edges. Also, if you can't add $ k $ edges of weight $ k + 1 $ , you can't choose such $ k $ .For example, if you can add $ 5 $ more edges to the graph of weight $ 6 $ , you may add them, and it will cost $ 6 $ for the whole pack of $ 5 $ edges. But if you can only add $ 4 $ edges of weight $ 6 $ to the graph, you can't perform this operation for $ k = 5 $ . Given two integers $ n $ and $ m $ , find the minimum total cost to form a graph of $ n $ vertices and exactly $ m $ edges using the operation above. If such a graph can't be constructed, output $ -1 $ . Note that the final graph may consist of several connected components.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 10^4 $ ). Description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 2 \leq n \leq 10^6 $ ; $ 1 \leq m \leq \frac{n(n-1)}{2} $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each test case, print the minimum cost to build the graph, or $ -1 $ if you can't build such a graph.

输入输出样例

输入样例 #1

4
4 1
6 10
9 4
10 11

输出样例 #1

2
-1
7
21

说明

In the first test case, we can add an edge between the vertices $ 2 $ and $ 4 $ with $ \gcd = 2 $ . This is the only possible way to add $ 1 $ edge that will cost $ 2 $ . In the second test case, there is no way to add $ 10 $ edges, so the answer is $ -1 $ . In the third test case, we can add the following edges: - $ k = 1 $ : edge of weight $ 2 $ between vertices $ 2 $ and $ 4 $ ( $ \gcd(2, 4) = 2 $ ). Cost: $ 2 $ ; - $ k = 1 $ : edge of weight $ 2 $ between vertices $ 4 $ and $ 6 $ ( $ \gcd(4, 6) = 2 $ ). Cost: $ 2 $ ; - $ k = 2 $ : edges of weight $ 3 $ : $ (3, 6) $ and $ (3, 9) $ ( $ \gcd(3, 6) = \gcd(3, 9) = 3 $ ). Cost: $ 3 $ . As a result, we added $ 1 + 1 + 2 = 4 $ edges with total cost $ 2 + 2 + 3 = 7 $ , which is the minimal possible 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 $ 的边，你可以添加它们，这将为这 $ 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 $。**题目大意**： 给定一个初始为空的、含有 $ 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 $ 的边，你可以添加它们，这将为这 $ 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 $。