Vulnerable Kerbals
题意翻译
### 题目描述
给出两个整数 $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$。
题目描述
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<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] $ .