1514C.md (1185B)
1 Source: https://codeforces.com/problemset/problem/1514/C 2 3 C. Product 1 Modulo N 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Now you get Baby Ehab's first words: "Given an integer $n$, find the longest subsequence of $[1,2, \ldots, n-1]$ whose product is $1$ modulo $n$." Please solve the problem. 22 23 A sequence $b$ is a subsequence of an array $a$ if $b$ can be obtained from $a$ by deleting some (possibly all) elements. The product of an empty subsequence is equal to $1$. 24 25 Input 26 27 The only line contains the integer $n$ ($2 \le n \le 10^5$). 28 29 Output 30 31 The first line should contain a single integer, the length of the longest subsequence. 32 33 The second line should contain the elements of the subsequence, in increasing order. 34 35 If there are multiple solutions, you can print any. 36 37 Examples 38 39 Input 40 41 ``` 42 5 43 ``` 44 45 Output 46 47 ``` 48 3 49 1 2 3 50 ``` 51 52 Input 53 54 ``` 55 8 56 ``` 57 58 Output 59 60 ``` 61 4 62 1 3 5 7 63 ``` 64 65 Note 66 67 In the first example, the product of the elements is $6$ which is congruent to $1$ modulo $5$. The only longer subsequence is $[1,2,3,4]$. Its product is $24$ which is congruent to $4$ modulo $5$. Hence, the answer is $[1,2,3]$.