Product 1 Modulo N (Codeforces 1514C)
Tags: Greedy, number theory

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

Input: The only line contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

Output: The first line should contain a single integer, the length of the longest subsequence.The second line should contain the elements of the subsequence, in increasing order.If there are multiple solutions, you can print any.

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

Sample Inputs:
5

8

Sample Outputs:
3
1 2 3

4
1 3 5 7

Solution (Python):
import math
n = int(input())
coprimes = [False] * n
prod = 1
for i in range(1, n):
    if math.gcd(i, n) == 1:
        coprimes[i] = True
        prod = prod * i % n
if prod != 1:
    coprimes[prod] = False
print(sum(coprimes))
print(' '.join([str(A) for A in range(1, n) if coprimes[A]]))

Solution (Python):
from sys import stdin, stdout
get_string = lambda : stdin.readline().strip(' ')
get_intmap = lambda : map(int, get_string().split(' '))

def testcase():
    n = n1 = int(input())
    prime_factors = []
    for i in range(2, int(n ** 0.5) + 4):
        (q, r) = divmod(n1, i)
        if r == 0:
            prime_factors.append(i)
            while r == 0:
                n1 = q
                (q, r) = divmod(n1, i)
    if n1 > 1:
        prime_factors.append(n1)
    (coprimes, prod) = ([], 1)
    for i in range(1, n):
        ok = True
        for prime in prime_factors:
            ok = i % prime
            if prime > i or not ok:
                break
        if ok:
            coprimes.append(i)
            prod = prod * i % n
    if prod != 1:
        coprimes.remove(prod)
    print(len(coprimes))
    print(' '.join([str(i) for i in coprimes]))
testcase()
quit()
for t in range(int(input())):
    testcase()

Solution (Python):
import math
n = int(input())
prod = 1
l = [1]
for k in range(2, n - 1):
    if math.gcd(n, k) == 1:
        prod = prod * k % n
        l.append(k)
if prod != 1:
    l.append(n - 1)
print(len(l))
print(' '.join(map(str, l)))