English · Original
Chinese · Translation
Formal · Original
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.
## Input
The first line of input contains two integers _n_ and _m_ (0 ≤ _n_ < _m_ ≤ 200 000) — 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.
## Output
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.
[samples]
## Note
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\].
给定一个整数 $m$，以及一个包含 $n$ 个互不相同的整数的列表，这些整数介于 $0$ 和 $m - 1$ 之间。
你需要构造一个满足以下性质的序列：
构造任意一个满足上述性质的序列。
输入的第一行包含两个整数 $n$ 和 $m$ ($0 ≤ n < m ≤ 200 000$) —— 分别表示禁止的前缀积的个数和模数。
如果 $n$ 非零，则输入的下一行包含 $n$ 个介于 $0$ 和 $m - 1$ 之间的互不相同的整数，表示禁止的前缀积。如果 $n$ 为零，则该行不存在。
第一行输出一个整数 $k$，表示你构造的序列的长度。
第二行输出 $k$ 个用空格分隔的整数，表示你构造的序列。
对于第一个样例，该序列的前缀积对 $m$ 取模的结果为 $[1, 2, 3, 4, 0]$。
对于第二个样例，该序列的前缀积对 $m$ 取模的结果为 $[3, 7, 4, 6, 8, 0]$。
## Input
输入的第一行包含两个整数 $n$ 和 $m$ ($0 ≤ n < m ≤ 200 000$) —— 分别表示禁止的前缀积的个数和模数。如果 $n$ 非零，则输入的下一行包含 $n$ 个介于 $0$ 和 $m - 1$ 之间的互不相同的整数，表示禁止的前缀积。如果 $n$ 为零，则该行不存在。
## Output
第一行输出一个整数 $k$，表示你构造的序列的长度。第二行输出 $k$ 个用空格分隔的整数，表示你构造的序列。
[samples]
## Note
对于第一个样例，该序列的前缀积对 $m$ 取模的结果为 $[1, 2, 3, 4, 0]$。对于第二个样例，该序列的前缀积对 $m$ 取模的结果为 $[3, 7, 4, 6, 8, 0]$。
**Definitions**
Let $ n, m \in \mathbb{Z} $ with $ 0 \leq n < m \leq 200{,}000 $.
Let $ F \subseteq \{0, 1, \dots, m-1\} $ be the set of forbidden prefix products, with $ |F| = n $.
**Constraints**
1. $ 0 \leq n < m \leq 200{,}000 $
2. All elements of $ F $ are distinct and satisfy $ 0 \leq f < m $ for all $ f \in F $.
3. The sequence $ a = (a_1, a_2, \dots, a_k) $ must satisfy:
- Each $ a_i \in \{1, 2, \dots, m-1\} $
- The prefix products $ p_j = \left( \prod_{i=1}^j a_i \right) \bmod m $ for $ j = 1, \dots, k $
- $ p_j \notin F $ for all $ j < k $
- $ p_k = 0 $
**Objective**
Construct a sequence $ a = (a_1, \dots, a_k) $ of minimal possible length $ k $ such that:
- All prefix products modulo $ m $ avoid $ F $ until the final one,
- The final prefix product is $ 0 \bmod m $,
- The sequence consists of integers in $ \{1, 2, \dots, m-1\} $.
API Response (JSON)
{
"problem": {
"name": "E. Vulnerable Kerbals",
"description": {
"content": "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 an",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF801E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given an integer _m_, and a list of _n_ distinct integers between 0 and _m_ - 1.\n\nYou would like to construct a sequence satisfying the properties:\n\n* Each element is an integer between 0 an...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "给定一个整数 $m$，以及一个包含 $n$ 个互不相同的整数的列表，这些整数介于 $0$ 和 $m - 1$ 之间。\n\n你需要构造一个满足以下性质的序列：\n\n构造任意一个满足上述性质的序列。\n\n输入的第一行包含两个整数 $n$ 和 $m$ ($0 ≤ n < m ≤ 200 000$) —— 分别表示禁止的前缀积的个数和模数。\n\n如果 $n$ 非零，则输入的下一行包含 $n$ 个介于 $0$ 和 ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z} $ with $ 0 \\leq n < m \\leq 200{,}000 $. \nLet $ F \\subseteq \\{0, 1, \\dots, m-1\\} $ be the set of forbidden prefix products, with $ |F| = n $. \n\n**Constrain...",
"is_translate": false,
"language": "Formal"
}
]
}