Three Days Grace

题面翻译

题目大意

给定一个初始有 $n$ 个元素的可重复集合 $A$，其中每个元素都在 $1$ 到 $m$ 之间。

每次操作可以将 $A$ 中的一个元素（称之为 $x$）从 $A$ 中删除，然后在 $A$ 中加入两个元素 $p,q$，满足 $p\cdot q=x$ 且 $p,q>1$。

显然每次操作后 $A$ 的大小会增加 $1$。

定义 $A$ 的平衡值为 $A$ 中的最大值减去最小值，求任意次操作（可以是 $0$ 次）后最小可能的平衡值。

输入格式

第一行输入一个整数 $T (1\leq T\leq 10^5)$，表示测试数据组数。

每个测试数据包含两行。

对于每个测试数据：

第一行包含两个整数 $n(1\leq n\leq 10^6)$, $m(1\leq m\leq 5\cdot 10^6)$，分别表示数组 $A$ 的元素个数以及 $A$ 中元素的最大可能值。

保证所有测试数据中的 $T$ 个 $n$ 之和不超过 $10^6$，所有测试数据中的 $T$ 个 $m$ 之和不超过 $5\cdot 10^6$。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n(1\leq a_i\leq 5\cdot 10^6)$。

输出格式

对于每个测试数据，输出一行一个整数，表示最小可能平衡值。

题目描述

Ibti was thinking about a good title for this problem that would fit the round theme (numerus ternarium). He immediately thought about the third derivative, but that was pretty lame so he decided to include the best band in the world — Three Days Grace.

You are given a multiset $A$ with initial size $n$ , whose elements are integers between $1$ and $m$ . In one operation, do the following:

• select a value $x$ from the multiset $A$ , then
• select two integers $p$ and $q$ such that $p, q > 1$ and $p \cdot q = x$ . Insert $p$ and $q$ to $A$ , delete $x$ from $A$ .

Note that the size of the multiset $A$ increases by $1$ after each operation.

We define the balance of the multiset $A$ as $\max(a_i) - \min(a_i)$ . Find the minimum possible balance after performing any number (possible zero) of operations.

输入格式

The first line of the input contains a single integer $t$ ( $1 \le t \le 10^5$ ) — the number of test cases.

The second line of each test case contains two integers $n$ and $m$ ( $1 \le n \le 10^6$ , $1 \le m \le 5 \cdot 10^6$ ) — the initial size of the multiset, and the maximum value of an element.

The third line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le m$ ) — the elements in the initial multiset.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^6$ and the sum of $m$ across all test cases does not exceed $5 \cdot 10^6$ .

输出格式

For each test case, print a single integer — the minimum possible balance.

样例 #1

样例输入 #1

4
5 10
2 4 2 4 2
3 50
12 2 3
2 40
6 35
2 5
1 5

样例输出 #1

0
1
2
4

提示

In the first test case, we can apply the operation on each of the $4$ s with $(p,q) = (2,2)$ and make the multiset $\{2,2,2,2,2,2,2\}$ with balance $\max(\{2,2,2,2,2,2,2\}) - \min(\{2,2,2,2,2,2,2\}) = 0$ . It is obvious we cannot make this balance less than $0$ .

In the second test case, we can apply an operation on $12$ with $(p,q) = (3,4)$ . After this our multiset will be $\{3,4,2,3\}$ . We can make one more operation on $4$ with $(p,q) = (2,2)$ , making the multiset $\{3,2,2,2,3\}$ with balance equal to $1$ .

In the third test case, we can apply an operation on $35$ with $(p,q) = (5,7)$ . The final multiset is $\{6,5,7\}$ and has a balance equal to $7-5 = 2$ .

In the forth test case, we cannot apply any operation, so the balance is $5 - 1 = 4$ .

源码：

# Three Days Grace

## 题面翻译

### 题目大意  

给定一个初始有 $n$ 个元素的可重复集合 $A$，其中每个元素都在 $1$ 到 $m$ 之间。  

每次操作可以将 $A$ 中的一个元素（称之为 $x$）从 $A$ 中删除，然后在 $A$ 中加入两个元素 $p,q$，满足 $p\cdot q=x$ 且 $p,q>1$。

显然每次操作后 $A$ 的大小会增加 $1$。  

定义 $A$ 的平衡值为 $A$ 中的最大值减去最小值，求任意次操作（可以是 $0$ 次）后最小可能的平衡值。

### 输入格式  

第一行输入一个整数 $T (1\leq T\leq 10^5)$，表示测试数据组数。  

每个测试数据包含两行。 

对于每个测试数据：  

第一行包含两个整数 $n(1\leq n\leq 10^6)$, $m(1\leq m\leq 5\cdot 10^6)$，分别表示数组 $A$ 的元素个数以及 $A$ 中元素的最大可能值。

保证所有测试数据中的 $T$ 个 $n$ 之和不超过 $10^6$，所有测试数据中的 $T$ 个 $m$ 之和不超过 $5\cdot 10^6$。  

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n(1\leq a_i\leq 5\cdot 10^6)$。 

### 输出格式  

对于每个测试数据，输出一行一个整数，表示最小可能平衡值。

## 题目描述

Ibti was thinking about a good title for this problem that would fit the round theme (numerus ternarium). He immediately thought about the third derivative, but that was pretty lame so he decided to include the best band in the world — [Three Days Grace](https://www.youtube.com/channel/UCJDON3eLf8709E9YfjAgLOw).

You are given a multiset $ A $ with initial size $ n $ , whose elements are integers between $ 1 $ and $ m $ . In one operation, do the following:

- select a value $ x $ from the multiset $ A $ , then
- select two integers $ p $ and $ q $ such that $ p, q > 1 $ and $ p \cdot q = x $ . Insert $ p $ and $ q $ to $ A $ , delete $ x $ from $ A $ .

Note that the size of the multiset $ A $ increases by $ 1 $ after each operation.

We define the balance of the multiset $ A $ as $ \max(a_i) - \min(a_i) $ . Find the minimum possible balance after performing any number (possible zero) of operations.

## 输入格式

The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 10^5 $ ) — the number of test cases.

The second line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 10^6 $ , $ 1 \le m \le 5 \cdot 10^6 $ ) — the initial size of the multiset, and the maximum value of an element.

The third line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le m $ ) — the elements in the initial multiset.

It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 10^6 $ and the sum of $ m $ across all test cases does not exceed $ 5 \cdot 10^6 $ .

## 输出格式

For each test case, print a single integer — the minimum possible balance.

## 样例 #1

### 样例输入 #1

4 5 10 2 4 2 4 2 3 50 12 2 3 2 40 6 35 2 5 1 5

### 样例输出 #1

0 1 2 4

## 提示

In the first test case, we can apply the operation on each of the $ 4 $ s with $ (p,q) = (2,2) $ and make the multiset $ \{2,2,2,2,2,2,2\} $ with balance $ \max(\{2,2,2,2,2,2,2\}) - \min(\{2,2,2,2,2,2,2\}) = 0 $ . It is obvious we cannot make this balance less than $ 0 $ .

In the second test case, we can apply an operation on $ 12 $ with $ (p,q) = (3,4) $ . After this our multiset will be $ \{3,4,2,3\} $ . We can make one more operation on $ 4 $ with $ (p,q) = (2,2) $ , making the multiset $ \{3,2,2,2,3\} $ with balance equal to $ 1 $ .

In the third test case, we can apply an operation on $ 35 $ with $ (p,q) = (5,7) $ . The final multiset is $ \{6,5,7\} $ and has a balance equal to $ 7-5 = 2 $ .

In the forth test case, we cannot apply any operation, so the balance is $ 5 - 1 = 4 $ .