← 返回题目列表

Codeforces · 1513/D

D. GCD 和 MST

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

给定一个由 $$$n$$$ ($$$n \geq 2$$$) 个正整数组成的数组 $$$a$$$ 和一个整数 $$$p$$$。考虑 $$$n$$$ 顶点的无向加权图,编号从 $$$1$$$ 到 $$$n$$$,其中顶点 $$$i$$$ 和 $$$j$$$ ($$$i<j$$$) 之间的边按以下方式添加:

- 如果 $$$gcd(a_i, a_{i+1}, a_{i+2}, \dots, a_{j}) = min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$$$,则存在权重 $$$min(a_i, a_{i+1}, a_{i+2}) 的边, \dots, a_j)$$$ 介于 $$$i$$$ 和 $$$j$$$ 之间。
- 如果 $$$i+1=j$$$,则 $$$i$$$ 和 $$$j$$$ 之间存在权重 $$$p$$$ 的边缘。

这里 $$$gcd(x, y, \ldots)$$$ 表示整数 $$$x$$$, $$$y$$$, .... 的最大公约数 (GCD)

请注意,如果上述两个条件都成立,则 $$$i$$$ 和 $$$j$$$ 之间可能存在多条边,并且如果 $$$i$$$ 和 $$$j$$$ 的两个条件均不成立,则这些顶点之间没有边。

目标是找到该图的最小生成树的权重。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) 和 $$$p$$$ ($$$1 \leq p \leq 10^9$$$) - 节点数和参数 $$$p$$$。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

输出 $$$t$$$ 行。对于每个测试用例,打印相应图表的权重。

示例

输入 #1

4
2 5
10 10
2 5
3 3
4 5
5 2 4 9
8 8
5 3 3 6 10 100 9 15

输出 #1

5
3
12
46

注意

以下是该示例的四个测试用例的图表(图表中可能的 MST 的边缘标记为粉红色):

对于测试用例 1

对于测试用例 2

对于测试用例 3

对于测试用例 4