codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.