309949: CF1764B. Doremy's Perfect Math Class
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Doremy's Perfect Math Class
题意翻译
给定一个正整数集合 $S$。对于 $S$，你可以执行以下操作若干次： - 从集合中选两个数 $x$ 和 $y$，使得 $x$ 和 $y$ 满足 $x>y$ 并且 $x-y$ 不在集合 $S$ 中。 - 将 $x-y$ 作为一个新元素加入到集合中。 假设操作方式是最优的，输出到无法操作时集合 $S$ 的最大长度。题目保证结果有限。题目描述
"Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class. You are given a set $ S $ containing positive integers. You may perform the following operation some (possibly zero) number of times: - choose two integers $ x $ and $ y $ from the set $ S $ such that $ x > y $ and $ x - y $ is not in the set $ S $ . - add $ x-y $ into the set $ S $ . You need to tell Doremy the maximum possible number of integers in $ S $ if the operations are performed optimally. It can be proven that this number is finite.输入输出格式
输入格式
The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line contains an integer $ n $ ( $ 2 \le n\le 10^5 $ ) — the size of the set $ S $ . The second line contains $ n $ integers $ a_1,a_2,\dots,a_n $ ( $ 1\le a_1 < a_2 < \cdots < a_n \le 10^9 $ ) — the positive integers in $ S $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .
输出格式
For each test case, you need to output the maximum possible number of integers in $ S $ . It can be proven that this value is finite.
输入输出样例
输入样例 #1
2
2
1 2
3
5 10 25输出样例 #1
2
5说明
In the first test case, no such $ x $ and $ y $ exist. The maximum possible number of integers in $ S $ is $ 2 $ . In the second test case, - $ S=\{5,10,25\} $ at first. You can choose $ x=25 $ , $ y=10 $ , then add $ x-y=15 $ to the set. - $ S=\{5,10,15,25\} $ now. You can choose $ x=25 $ , $ y=5 $ , then add $ x-y=20 $ to the set. - $ S=\{5,10,15,20,25\} $ now. You can not perform any operation now. After performing all operations, the number of integers in $ S $ is $ 5 $ . It can be proven that no other sequence of operations allows $ S $ to contain more than $ 5 $ integers.Input
题意翻译
给定一个正整数集合 $S$。对于 $S$，你可以执行以下操作若干次： - 从集合中选两个数 $x$ 和 $y$，使得 $x$ 和 $y$ 满足 $x>y$ 并且 $x-y$ 不在集合 $S$ 中。 - 将 $x-y$ 作为一个新元素加入到集合中。 假设操作方式是最优的，输出到无法操作时集合 $S$ 的最大长度。题目保证结果有限。Output
**题意翻译**
给定一个正整数集合 $ S $。对于 $ S $，你可以执行以下操作若干次：
- 从集合中选两个数 $ x $ 和 $ y $，使得 $ x>y $ 并且 $ x-y $ 不在集合 $ S $ 中。
- 将 $ x-y $ 作为一个新元素加入到集合中。
假设操作方式是最优的，输出到无法操作时集合 $ S $ 的最大长度。题目保证结果有限。
**题目描述**
"Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class.
You are given a set $ S $ containing positive integers. You may perform the following operation some (possibly zero) number of times:
- choose two integers $ x $ and $ y $ from the set $ S $ such that $ x > y $ and $ x - y $ is not in the set $ S $ .
- add $ x-y $ into the set $ S $ .
You need to tell Doremy the maximum possible number of integers in $ S $ if the operations are performed optimally. It can be proven that this number is finite.
**输入输出格式**
**输入格式**
输入由多个测试案例组成。第一行包含一个整数 $ t $ ( $ 1\le t\le 10^4 $ ) —— 测试案例的数量。接下来是每个测试案例的描述。
第一行包含一个整数 $ n $ ( $ 2 \le n\le 10^5 $ ) —— 集合 $ S $ 的大小。
第二行包含 $ n $ 个整数 $ a_1,a_2,\dots,a_n $ ( $ 1\le a_1 < a_2 < \cdots < a_n \le 10^9 $ ) —— 集合 $ S $ 中的正整数。
保证所有测试案例中 $ n $ 的总和不超过 $ 2\cdot 10^5 $ 。
**输出格式**
对于每个测试案例，你需要输出执行最优操作后集合 $ S $ 中可能的最大整数数量。可以证明这个值是有限的。
**输入输出样例**
**输入样例 #1**
```
2
2
1 2
3
5 10 25
```
**输出样例 #1**
```
2
5
```
**说明**
在第一个测试案例中，不存在这样的 $ x $ 和 $ y $。集合 $ S $ 中可能的最大整数数量是 $ 2 $。
在第二个测试案例中，
- 初始时 $ S=\{5,10,25\} $。你可以选择 $ x=25 $, $ y=10 $，然后将 $ x-y=15 $ 加入到集合中。
- 现在 $ S=\{5,10,15,25\} $。你可以选择 $ x=25 $, $ y=5 $，然后将 $ x-y=20 $ 加入到集合中。
- 现在 $ S=\{5,10,15,20,25\} $。你现在不能执行任何操作。
执行所有操作后，集合 $ S $ 中的整数数量是 $ 5 $。可以证明，没有其他操作序列可以使 $ S $ 包含超过 $ 5 $ 个整数。**题意翻译** 给定一个正整数集合 $ S $。对于 $ S $，你可以执行以下操作若干次： - 从集合中选两个数 $ x $ 和 $ y $，使得 $ x>y $ 并且 $ x-y $ 不在集合 $ S $ 中。 - 将 $ x-y $ 作为一个新元素加入到集合中。 假设操作方式是最优的，输出到无法操作时集合 $ S $ 的最大长度。题目保证结果有限。 **题目描述** "Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class. You are given a set $ S $ containing positive integers. You may perform the following operation some (possibly zero) number of times: - choose two integers $ x $ and $ y $ from the set $ S $ such that $ x > y $ and $ x - y $ is not in the set $ S $ . - add $ x-y $ into the set $ S $ . You need to tell Doremy the maximum possible number of integers in $ S $ if the operations are performed optimally. It can be proven that this number is finite. **输入输出格式** **输入格式** 输入由多个测试案例组成。第一行包含一个整数 $ t $ ( $ 1\le t\le 10^4 $ ) —— 测试案例的数量。接下来是每个测试案例的描述。 第一行包含一个整数 $ n $ ( $ 2 \le n\le 10^5 $ ) —— 集合 $ S $ 的大小。 第二行包含 $ n $ 个整数 $ a_1,a_2,\dots,a_n $ ( $ 1\le a_1 < a_2 < \cdots < a_n \le 10^9 $ ) —— 集合 $ S $ 中的正整数。 保证所有测试案例中 $ n $ 的总和不超过 $ 2\cdot 10^5 $ 。 **输出格式** 对于每个测试案例，你需要输出执行最优操作后集合 $ S $ 中可能的最大整数数量。可以证明这个值是有限的。 **输入输出样例** **输入样例 #1** ``` 2 2 1 2 3 5 10 25 ``` **输出样例 #1** ``` 2 5 ``` **说明** 在第一个测试案例中，不存在这样的 $ x $ 和 $ y $。集合 $ S $ 中可能的最大整数数量是 $ 2 $。 在第二个测试案例中， - 初始时 $ S=\{5,10,25\} $。你可以选择 $ x=25 $, $ y=10 $，然后将 $ x-y=15 $ 加入到集合中。 - 现在 $ S=\{5,10,15,25\} $。你可以选择 $ x=25 $, $ y=5 $，然后将 $ x-y=20 $ 加入到集合中。 - 现在 $ S=\{5,10,15,20,25\} $。你现在不能执行任何操作。 执行所有操作后，集合 $ S $ 中的整数数量是 $ 5 $。可以证明，没有其他操作序列可以使 $ S $ 包含超过 $ 5 $ 个整数。
给定一个正整数集合 $ S $。对于 $ S $，你可以执行以下操作若干次：
- 从集合中选两个数 $ x $ 和 $ y $，使得 $ x>y $ 并且 $ x-y $ 不在集合 $ S $ 中。
- 将 $ x-y $ 作为一个新元素加入到集合中。
假设操作方式是最优的，输出到无法操作时集合 $ S $ 的最大长度。题目保证结果有限。
**题目描述**
"Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class.
You are given a set $ S $ containing positive integers. You may perform the following operation some (possibly zero) number of times:
- choose two integers $ x $ and $ y $ from the set $ S $ such that $ x > y $ and $ x - y $ is not in the set $ S $ .
- add $ x-y $ into the set $ S $ .
You need to tell Doremy the maximum possible number of integers in $ S $ if the operations are performed optimally. It can be proven that this number is finite.
**输入输出格式**
**输入格式**
输入由多个测试案例组成。第一行包含一个整数 $ t $ ( $ 1\le t\le 10^4 $ ) —— 测试案例的数量。接下来是每个测试案例的描述。
第一行包含一个整数 $ n $ ( $ 2 \le n\le 10^5 $ ) —— 集合 $ S $ 的大小。
第二行包含 $ n $ 个整数 $ a_1,a_2,\dots,a_n $ ( $ 1\le a_1 < a_2 < \cdots < a_n \le 10^9 $ ) —— 集合 $ S $ 中的正整数。
保证所有测试案例中 $ n $ 的总和不超过 $ 2\cdot 10^5 $ 。
**输出格式**
对于每个测试案例，你需要输出执行最优操作后集合 $ S $ 中可能的最大整数数量。可以证明这个值是有限的。
**输入输出样例**
**输入样例 #1**
```
2
2
1 2
3
5 10 25
```
**输出样例 #1**
```
2
5
```
**说明**
在第一个测试案例中，不存在这样的 $ x $ 和 $ y $。集合 $ S $ 中可能的最大整数数量是 $ 2 $。
在第二个测试案例中，
- 初始时 $ S=\{5,10,25\} $。你可以选择 $ x=25 $, $ y=10 $，然后将 $ x-y=15 $ 加入到集合中。
- 现在 $ S=\{5,10,15,25\} $。你可以选择 $ x=25 $, $ y=5 $，然后将 $ x-y=20 $ 加入到集合中。
- 现在 $ S=\{5,10,15,20,25\} $。你现在不能执行任何操作。
执行所有操作后，集合 $ S $ 中的整数数量是 $ 5 $。可以证明，没有其他操作序列可以使 $ S $ 包含超过 $ 5 $ 个整数。**题意翻译** 给定一个正整数集合 $ S $。对于 $ S $，你可以执行以下操作若干次： - 从集合中选两个数 $ x $ 和 $ y $，使得 $ x>y $ 并且 $ x-y $ 不在集合 $ S $ 中。 - 将 $ x-y $ 作为一个新元素加入到集合中。 假设操作方式是最优的，输出到无法操作时集合 $ S $ 的最大长度。题目保证结果有限。 **题目描述** "Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class. You are given a set $ S $ containing positive integers. You may perform the following operation some (possibly zero) number of times: - choose two integers $ x $ and $ y $ from the set $ S $ such that $ x > y $ and $ x - y $ is not in the set $ S $ . - add $ x-y $ into the set $ S $ . You need to tell Doremy the maximum possible number of integers in $ S $ if the operations are performed optimally. It can be proven that this number is finite. **输入输出格式** **输入格式** 输入由多个测试案例组成。第一行包含一个整数 $ t $ ( $ 1\le t\le 10^4 $ ) —— 测试案例的数量。接下来是每个测试案例的描述。 第一行包含一个整数 $ n $ ( $ 2 \le n\le 10^5 $ ) —— 集合 $ S $ 的大小。 第二行包含 $ n $ 个整数 $ a_1,a_2,\dots,a_n $ ( $ 1\le a_1 < a_2 < \cdots < a_n \le 10^9 $ ) —— 集合 $ S $ 中的正整数。 保证所有测试案例中 $ n $ 的总和不超过 $ 2\cdot 10^5 $ 。 **输出格式** 对于每个测试案例，你需要输出执行最优操作后集合 $ S $ 中可能的最大整数数量。可以证明这个值是有限的。 **输入输出样例** **输入样例 #1** ``` 2 2 1 2 3 5 10 25 ``` **输出样例 #1** ``` 2 5 ``` **说明** 在第一个测试案例中，不存在这样的 $ x $ 和 $ y $。集合 $ S $ 中可能的最大整数数量是 $ 2 $。 在第二个测试案例中， - 初始时 $ S=\{5,10,25\} $。你可以选择 $ x=25 $, $ y=10 $，然后将 $ x-y=15 $ 加入到集合中。 - 现在 $ S=\{5,10,15,25\} $。你可以选择 $ x=25 $, $ y=5 $，然后将 $ x-y=20 $ 加入到集合中。 - 现在 $ S=\{5,10,15,20,25\} $。你现在不能执行任何操作。 执行所有操作后，集合 $ S $ 中的整数数量是 $ 5 $。可以证明，没有其他操作序列可以使 $ S $ 包含超过 $ 5 $ 个整数。