Vulnerable Kerbals

题意翻译

给出m,n，再给一个m个数的集合让你构造一个序列满足以下的条件： 1.这个序列的所有数都在0-m-1之间（含） 2.这个数列的所有前缀积都不同 3.所有的前缀积都不能出现在给你的集合中 4.最大化这个序列的长度 输出任意满足条件的序列。

题目描述

You are given an integer $ m $ , and a list of $ n $ distinct integers between $ 0 $ and $ m-1 $ . You would like to construct a sequence satisfying the properties: - Each element is an integer between $ 0 $ and $ m-1 $ , inclusive. - All prefix products of the sequence modulo $ m $ are distinct. - No prefix product modulo $ m $ appears as an element of the input list. - The length of the sequence is maximized. Construct any sequence satisfying the properties above.

输入输出格式

输入格式

The first line of input contains two integers $ n $ and $ m $ ( $ 0<=n&lt;m<=200000 $ ) — the number of forbidden prefix products and the modulus. If $ n $ is non-zero, the next line of input contains $ n $ distinct integers between $ 0 $ and $ m-1 $ , the forbidden prefix products. If $ n $ is zero, this line doesn't exist.

输出格式

On the first line, print the number $ k $ , denoting the length of your sequence. On the second line, print $ k $ space separated integers, denoting your sequence.

输入输出样例

输入样例 #1

0 5

输出样例 #1

5
1 2 4 3 0

输入样例 #2

3 10
2 9 1

输出样例 #2

6
3 9 2 9 8 0

说明

For the first case, the prefix products of this sequence modulo $ m $ are $ [1,2,3,4,0] $ . For the second case, the prefix products of this sequence modulo $ m $ are $ [3,7,4,6,8,0] $ .

题意翻译

### 题目描述 给出两个整数 $n, m$，在给出一个大小为 $n$ 的集合 $B$，且 $\forall y \in B$ 有 $0 \leq y < m$。现要求构造一个序列 $A$，满足以下条件： - $\forall x \in A$ 有 $0 \leq x < m$。 - $\forall i, j, 1 \leq i, j \leq |A|$， 有 $\prod \limits _{k = 1}^{i}A_k \not\equiv \prod \limits _{k = 1}^{j}A_k \pmod m$ - $\forall i, y, 1 \leq i \leq |A|, y \in B$， 有 $\prod \limits _{k = 1}^{i}A_k \not\equiv y \pmod m$ 在序列 $A$ 合法的条件下满足长度最大化，并给出一种构造方案。 ### 输入格式 第一行两个整数 $n, m$。 第二行（若 $n = 0$ 则没有）输入 $n$ 个整数，表示集合 $B$。 ### 输出格式 第一行一个整数，表示序列 $A$ 的最大长度 $|A|$。 第二行 $|A|$ 个整数，表示序列 $A$。 ### 数据范围 $0 \leq n, m \leq 2 \times 10^5$。