309470: CF1684G. Euclid Guess
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Euclid Guess
题意翻译
### 题目描述 下面是一个经过部分改动的求 $\gcd$ 的伪代码（其中 $t$ 是一个初始为空的序列）： ```plain function Euclid(a, b): if a < b: swap(a, b) if b == 0: return a r = reminder from dividing a by b (即设 r 为 a mod b) if r > 0: append r to the back of t (即将 r 插入到 t 的尾部) return Euclid(b, r) ``` 有一个由数对构成的序列 $p$，接下来我们对 $p$ 中每个数对都执行一次上述函数，然后把 $t$ 重新排列并给定到输入中。 给定 $n,m$ 和长度为 $n$ 的序列 $t$。 你需要构造一个长度不超过 $2\times10^4$ 的数对序列 $p$，满足： - 每个数对中的元素都是不超过 $m$ 的正整数。 - 根据序列 $p$ 可以经过上述操作得到输入中给定的 $t$。 有解输出任意一组解，无解输出 `-1`。 ### 输入格式 第一行输入两个整数 $n,m(1\leq n\leq10^3;1\leq m\leq10^9)$。 接下来一行输入 $n$ 个整数表示 $t_1,t_2,\cdots,t_n(1\leq t_i\leq m)$。 ### 输出格式 如果无解，输出一行 `-1`。 否则，首先输出一行一个整数 $k(1\leq k\leq2\times10^4)$ 表示你构造的 $p$ 的长度。 接下来输出 $k$ 行，其中第 $i$ 行输出两个整数 $a_i,b_i(1\leq a_i,b_i\leq m)$ 表示 $p$ 中第 $i$ 个数对。 ### 样例解释 对于样例一： - 数对 $(19,11)$ 会将 $8,3,2,1$ 四个数插入到 $t$ 中。 - 数对 $(15,9)$ 会将 $6,3$ 两个数插入到 $t$ 中。 - 数对 $(3,7)$ 会将 $1$ 这个数插入到 $t$ 中。 最终 $t=[8,3,2,1,6,3,1]$，经过重新排列后可以得到输入中给定的 $[1,8,1,6,3,2,3]$。题目描述
Let's consider Euclid's algorithm for finding the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor), where $ t $ is a list: ``` <pre class="verbatim"><br></br>function Euclid(a, b):<br></br> if a < b:<br></br> swap(a, b)<br></br><br></br> if b == 0:<br></br> return a<br></br><br></br> r = reminder from dividing a by b<br></br> if r > 0:<br></br> append r to the back of t<br></br><br></br> return Euclid(b, r)<br></br> ``` There is an array $ p $ of pairs of positive integers that are not greater than $ m $ . Initially, the list $ t $ is empty. Then the function is run on each pair in $ p $ . After that the list $ t $ is shuffled and given to you. You have to find an array $ p $ of any size not greater than $ 2 \cdot 10^4 $ that produces the given list $ t $ , or tell that no such array exists.输入输出格式
输入格式
The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 10^3 $ , $ 1 \le m \le 10^9 $ ) — the length of the array $ t $ and the constraint for integers in pairs. The second line contains $ n $ integers $ t_1, t_2, \ldots, t_n $ ( $ 1 \le t_i \le m $ ) — the elements of the array $ t $ .
输出格式
- If the answer does not exist, output $ -1 $ . - If the answer exists, in the first line output $ k $ ( $ 1 \le k \le 2 \cdot 10^4 $ ) — the size of your array $ p $ , i. e. the number of pairs in the answer. The $ i $ -th of the next $ k $ lines should contain two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i, b_i \le m $ ) — the $ i $ -th pair in $ p $ . If there are multiple valid answers you can output any of them.
输入输出样例
输入样例 #1
7 20
1 8 1 6 3 2 3输出样例 #1
3
19 11
15 9
3 7输入样例 #2
2 10
7 1输出样例 #2
-1输入样例 #3
2 15
1 7输出样例 #3
1
15 8输入样例 #4
1 1000000000
845063470输出样例 #4
-1说明
In the first sample let's consider the array $ t $ for each pair: - $ (19,\, 11) $ : $ t = [8, 3, 2, 1] $ ; - $ (15,\, 9) $ : $ t = [6, 3] $ ; - $ (3,\, 7) $ : $ t = [1] $ . So in total $ t = [8, 3, 2, 1, 6, 3, 1] $ , which is the same as the input $ t $ (up to a permutation). In the second test case it is impossible to find such array $ p $ of pairs that all integers are not greater than $ 10 $ and $ t = [7, 1] $ In the third test case for the pair $ (15,\, 8) $ array $ t $ will be $ [7, 1] $ .Input
题意翻译
### 题目描述 下面是一个经过部分改动的求 $\gcd$ 的伪代码（其中 $t$ 是一个初始为空的序列）： ```plain function Euclid(a, b): if a < b: swap(a, b) if b == 0: return a r = reminder from dividing a by b (即设 r 为 a mod b) if r > 0: append r to the back of t (即将 r 插入到 t 的尾部) return Euclid(b, r) ``` 有一个由数对构成的序列 $p$，接下来我们对 $p$ 中每个数对都执行一次上述函数，然后把 $t$ 重新排列并给定到输入中。 给定 $n,m$ 和长度为 $n$ 的序列 $t$。 你需要构造一个长度不超过 $2\times10^4$ 的数对序列 $p$，满足： - 每个数对中的元素都是不超过 $m$ 的正整数。 - 根据序列 $p$ 可以经过上述操作得到输入中给定的 $t$。 有解输出任意一组解，无解输出 `-1`。 ### 输入格式 第一行输入两个整数 $n,m(1\leq n\leq10^3;1\leq m\leq10^9)$。 接下来一行输入 $n$ 个整数表示 $t_1,t_2,\cdots,t_n(1\leq t_i\leq m)$。 ### 输出格式 如果无解，输出一行 `-1`。 否则，首先输出一行一个整数 $k(1\leq k\leq2\times10^4)$ 表示你构造的 $p$ 的长度。 接下来输出 $k$ 行，其中第 $i$ 行输出两个整数 $a_i,b_i(1\leq a_i,b_i\leq m)$ 表示 $p$ 中第 $i$ 个数对。 ### 样例解释 对于样例一： - 数对 $(19,11)$ 会将 $8,3,2,1$ 四个数插入到 $t$ 中。 - 数对 $(15,9)$ 会将 $6,3$ 两个数插入到 $t$ 中。 - 数对 $(3,7)$ 会将 $1$ 这个数插入到 $t$ 中。 最终 $t=[8,3,2,1,6,3,1]$，经过重新排列后可以得到输入中给定的 $[1,8,1,6,3,2,3]$。Output
**题意翻译**
**题目描述**
下面是一个经过部分改动的求 $\gcd$ 的伪代码（其中 $t$ 是一个初始为空的序列）：
```plaintext
function Euclid(a, b):
if a < b:
swap(a, b)
if b == 0:
return a
r = reminder from dividing a by b (即设 r 为 a mod b)
if r > 0:
append r to the back of t (即将 r 插入到 t 的尾部)
return Euclid(b, r)
```
有一个由数对构成的序列 $p$，接下来我们对 $p$ 中每个数对都执行一次上述函数，然后把 $t$ 重新排列并给定到输入中。
给定 $n,m$ 和长度为 $n$ 的序列 $t$。
你需要构造一个长度不超过 $2\times10^4$ 的数对序列 $p$，满足：
- 每个数对中的元素都是不超过 $m$ 的正整数。
- 根据序列 $p$ 可以经过上述操作得到输入中给定的 $t$。
有解输出任意一组解，无解输出 `-1`。
**输入格式**
第一行输入两个整数 $n,m(1\leq n\leq10^3;1\leq m\leq10^9)$。
接下来一行输入 $n$ 个整数表示 $t_1,t_2,\cdots,t_n(1\leq t_i\leq m)$。
**输出格式**
如果无解，输出一行 `-1`。
否则，首先输出一行一个整数 $k(1\leq k\leq2\times10^4)$ 表示你构造的 $p$ 的长度。
接下来输出 $k$ 行，其中第 $i$ 行输出两个整数 $a_i,b_i(1\leq a_i,b_i\leq m)$ 表示 $p$ 中第 $i$ 个数对。
**样例解释**
对于样例一：
- 数对 $(19,11)$ 会将 $8,3,2,1$ 四个数插入到 $t$ 中。
- 数对 $(15,9)$ 会将 $6,3$ 两个数插入到 $t$ 中。
- 数对 $(3,7)$ 会将 $1$ 这个数插入到 $t$ 中。
最终 $t=[8,3,2,1,6,3,1]$，经过重新排列后可以得到输入中给定的 $[1,8,1,6,3,2,3]$。**题意翻译** **题目描述** 下面是一个经过部分改动的求 $\gcd$ 的伪代码（其中 $t$ 是一个初始为空的序列）： ```plaintext function Euclid(a, b): if a < b: swap(a, b) if b == 0: return a r = reminder from dividing a by b (即设 r 为 a mod b) if r > 0: append r to the back of t (即将 r 插入到 t 的尾部) return Euclid(b, r) ``` 有一个由数对构成的序列 $p$，接下来我们对 $p$ 中每个数对都执行一次上述函数，然后把 $t$ 重新排列并给定到输入中。 给定 $n,m$ 和长度为 $n$ 的序列 $t$。 你需要构造一个长度不超过 $2\times10^4$ 的数对序列 $p$，满足： - 每个数对中的元素都是不超过 $m$ 的正整数。 - 根据序列 $p$ 可以经过上述操作得到输入中给定的 $t$。 有解输出任意一组解，无解输出 `-1`。 **输入格式** 第一行输入两个整数 $n,m(1\leq n\leq10^3;1\leq m\leq10^9)$。 接下来一行输入 $n$ 个整数表示 $t_1,t_2,\cdots,t_n(1\leq t_i\leq m)$。 **输出格式** 如果无解，输出一行 `-1`。 否则，首先输出一行一个整数 $k(1\leq k\leq2\times10^4)$ 表示你构造的 $p$ 的长度。 接下来输出 $k$ 行，其中第 $i$ 行输出两个整数 $a_i,b_i(1\leq a_i,b_i\leq m)$ 表示 $p$ 中第 $i$ 个数对。 **样例解释** 对于样例一： - 数对 $(19,11)$ 会将 $8,3,2,1$ 四个数插入到 $t$ 中。 - 数对 $(15,9)$ 会将 $6,3$ 两个数插入到 $t$ 中。 - 数对 $(3,7)$ 会将 $1$ 这个数插入到 $t$ 中。 最终 $t=[8,3,2,1,6,3,1]$，经过重新排列后可以得到输入中给定的 $[1,8,1,6,3,2,3]$。
**题目描述**
下面是一个经过部分改动的求 $\gcd$ 的伪代码（其中 $t$ 是一个初始为空的序列）：
```plaintext
function Euclid(a, b):
if a < b:
swap(a, b)
if b == 0:
return a
r = reminder from dividing a by b (即设 r 为 a mod b)
if r > 0:
append r to the back of t (即将 r 插入到 t 的尾部)
return Euclid(b, r)
```
有一个由数对构成的序列 $p$，接下来我们对 $p$ 中每个数对都执行一次上述函数，然后把 $t$ 重新排列并给定到输入中。
给定 $n,m$ 和长度为 $n$ 的序列 $t$。
你需要构造一个长度不超过 $2\times10^4$ 的数对序列 $p$，满足：
- 每个数对中的元素都是不超过 $m$ 的正整数。
- 根据序列 $p$ 可以经过上述操作得到输入中给定的 $t$。
有解输出任意一组解，无解输出 `-1`。
**输入格式**
第一行输入两个整数 $n,m(1\leq n\leq10^3;1\leq m\leq10^9)$。
接下来一行输入 $n$ 个整数表示 $t_1,t_2,\cdots,t_n(1\leq t_i\leq m)$。
**输出格式**
如果无解，输出一行 `-1`。
否则，首先输出一行一个整数 $k(1\leq k\leq2\times10^4)$ 表示你构造的 $p$ 的长度。
接下来输出 $k$ 行，其中第 $i$ 行输出两个整数 $a_i,b_i(1\leq a_i,b_i\leq m)$ 表示 $p$ 中第 $i$ 个数对。
**样例解释**
对于样例一：
- 数对 $(19,11)$ 会将 $8,3,2,1$ 四个数插入到 $t$ 中。
- 数对 $(15,9)$ 会将 $6,3$ 两个数插入到 $t$ 中。
- 数对 $(3,7)$ 会将 $1$ 这个数插入到 $t$ 中。
最终 $t=[8,3,2,1,6,3,1]$，经过重新排列后可以得到输入中给定的 $[1,8,1,6,3,2,3]$。**题意翻译** **题目描述** 下面是一个经过部分改动的求 $\gcd$ 的伪代码（其中 $t$ 是一个初始为空的序列）： ```plaintext function Euclid(a, b): if a < b: swap(a, b) if b == 0: return a r = reminder from dividing a by b (即设 r 为 a mod b) if r > 0: append r to the back of t (即将 r 插入到 t 的尾部) return Euclid(b, r) ``` 有一个由数对构成的序列 $p$，接下来我们对 $p$ 中每个数对都执行一次上述函数，然后把 $t$ 重新排列并给定到输入中。 给定 $n,m$ 和长度为 $n$ 的序列 $t$。 你需要构造一个长度不超过 $2\times10^4$ 的数对序列 $p$，满足： - 每个数对中的元素都是不超过 $m$ 的正整数。 - 根据序列 $p$ 可以经过上述操作得到输入中给定的 $t$。 有解输出任意一组解，无解输出 `-1`。 **输入格式** 第一行输入两个整数 $n,m(1\leq n\leq10^3;1\leq m\leq10^9)$。 接下来一行输入 $n$ 个整数表示 $t_1,t_2,\cdots,t_n(1\leq t_i\leq m)$。 **输出格式** 如果无解，输出一行 `-1`。 否则，首先输出一行一个整数 $k(1\leq k\leq2\times10^4)$ 表示你构造的 $p$ 的长度。 接下来输出 $k$ 行，其中第 $i$ 行输出两个整数 $a_i,b_i(1\leq a_i,b_i\leq m)$ 表示 $p$ 中第 $i$ 个数对。 **样例解释** 对于样例一： - 数对 $(19,11)$ 会将 $8,3,2,1$ 四个数插入到 $t$ 中。 - 数对 $(15,9)$ 会将 $6,3$ 两个数插入到 $t$ 中。 - 数对 $(3,7)$ 会将 $1$ 这个数插入到 $t$ 中。 最终 $t=[8,3,2,1,6,3,1]$，经过重新排列后可以得到输入中给定的 $[1,8,1,6,3,2,3]$。