https://codeforces.com/contest/1514/problem/C
시간 1초, 메모리 256MB

input :

• n (2 ≤ n ≤ 105)

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.
  두번째 줄에는 배열의 원소를 오름차순으로 출력합니다.

조건 :

• Given an integer n, find the longest subsequence of [1,2,…,n−1] whose product is 1 modulo n.
  n이 주어졌을 때 부분 배열의 모든 원소의 곱을 n으로 나눴을 때 나머지가 1이 되는 가장 긴 부분배열을 찾으시오.

---

나머지가 남아야 한다.
나머지가 남으려면 n과 동일한 약수를 가진 것들은 배열에 포함되면 안 된다.

이를 나타내는 방식이 서로소인것을 찾는 것이다.

서로소

서로소인 놈들을 다 일단 배열에 집어넣으면서 현재의 나머지가 몇인지 기록한다.
(나머지 * 숫자)에 대해 나머지를 구한다면 동일한 결과를 얻을 수 있다.
이를 모듈로 연산이라 하는 거 같은데 다음에 찾아보도록 하자.

마지막 결과

1이 아닌 경우가 발생할 수 있다.
그럴 때에 규칙이 존재하는데 자기자신을 제외하면 나머지가 1인 놈이 있다는 것이다.

사실 저 이유는 잘 모르겠다...
계산 결과를 통해 뒤에서 2번째 값에 자기 자신을 곱해서 제외를 하면 된다 하긴 하는데
그럴 때에 왜 2번째 놈의 결과는 1이 되는 건지 이걸 모르겠다.

import sys
import math

n = int(sys.stdin.readline())
ans = []
cnt = 1

for i in range(1, n):
    if math.gcd(i, n) == 1:
        cnt = (cnt * i) % n
        ans.append(i)

if cnt != 1:
    ans.pop()

print(len(ans))
print(*ans)