{"problem":{"name":"C. 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":"CF772C"},"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 and _m_ - 1, inclusive.\n*   All prefix products of the sequence modulo _m_ are distinct.\n*   No prefix product modulo _m_ appears as an element of the input list.\n*   The length of the sequence is maximized.\n\nConstruct any sequence satisfying the properties above.\n\n## Input\n\nThe first line of input contains two integers _n_ and _m_ (0 ≤ _n_ < _m_ ≤ 200 000) — the number of forbidden prefix products and the modulus.\n\nIf _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.\n\n## Output\n\nOn the first line, print the number _k_, denoting the length of your sequence.\n\nOn the second line, print _k_ space separated integers, denoting your sequence.\n\n[samples]\n\n## Note\n\nFor the first case, the prefix products of this sequence modulo _m_ are \\[1, 2, 3, 4, 0\\].\n\nFor the second case, the prefix products of this sequence modulo _m_ are \\[3, 7, 4, 6, 8, 0\\].","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$ 和 $m - 1$ 之间的互不相同的整数，即禁止的前缀积。如果 $n$ 为零，则该行不存在。\n\n第一行输出一个整数 $k$，表示你构造的序列的长度。\n\n第二行输出 $k$ 个用空格分隔的整数，表示你构造的序列。\n\n对于第一个样例，该序列的前缀积对 $m$ 取模的结果为 $[1, 2, 3, 4, 0]$。\n\n对于第二个样例，该序列的前缀积对 $m$ 取模的结果为 $[3, 7, 4, 6, 8, 0]$。\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $m$（$0 ≤ n < m ≤ 200 000$）—— 分别表示禁止的前缀积的个数和模数。如果 $n$ 非零，则输入的下一行包含 $n$ 个介于 $0$ 和 $m - 1$ 之间的互不相同的整数，即禁止的前缀积。如果 $n$ 为零，则该行不存在。\n\n## Output\n\n第一行输出一个整数 $k$，表示你构造的序列的长度。第二行输出 $k$ 个用空格分隔的整数，表示你构造的序列。\n\n[samples]\n\n## Note\n\n对于第一个样例，该序列的前缀积对 $m$ 取模的结果为 $[1, 2, 3, 4, 0]$。对于第二个样例，该序列的前缀积对 $m$ 取模的结果为 $[3, 7, 4, 6, 8, 0]$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ with $ 0 \\leq n < m \\leq 200000 $.  \nLet $ F \\subseteq \\{0, 1, \\dots, m-1\\} $ be the set of forbidden prefix products, with $ |F| = n $.  \n\n**Constraints**  \n1. $ 0 \\leq n < m \\leq 200000 $  \n2. All elements of $ F $ are distinct and satisfy $ 0 \\leq f < m $ for all $ f \\in F $.  \n3. The sequence $ a = (a_1, a_2, \\dots, a_k) $ must satisfy:  \n   - $ a_i \\in \\{1, 2, \\dots, m-1\\} $ for all $ i $  \n   - The prefix products $ p_j = \\left( \\prod_{i=1}^j a_i \\right) \\bmod m $ must avoid all values in $ F $ for $ j < k $, and $ p_k \\equiv 0 \\pmod{m} $  \n\n**Objective**  \nConstruct a sequence $ a = (a_1, a_2, \\dots, a_k) $ of minimal possible length $ k $ such that:  \n- $ p_j \\notin F $ for all $ j \\in \\{1, \\dots, k-1\\} $  \n- $ p_k \\equiv 0 \\pmod{m} $  \n\nOutput $ k $ and the sequence $ a $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF772C","tags":["constructive algorithms","dp","graphs","math","number theory"],"sample_group":[["0 5","5\n1 2 4 3 0"],["3 10\n2 9 1","6\n3 9 2 9 8 0"]],"created_at":"2026-03-03 11:00:39"}}