题意：给定一个n，从$1,2,3…,n-1$中选出最多个数，使得最后的乘积$prod\%n$=$1$。
分析：根据题意可知$prod=kn+1$，推得：$gcd(prod \% n , n) = gcd(prod , n) =1$，由此可知选出的数字必须与$n$互质，若选出的$i$不与$n$互质，那么最后$prod\%n!=1$，与要求不符。

记所有与n互质的数的集合为$A$，记$A$中所有数累乘的结果对$n$取模后的结果为$p$。

1. 若$p=1$，显然$A$中所有数都可以选；

2. 若$p≠1$，那么在选的时候将$p$跳过即可，最后的结果就为$1$。又因为$A$中所有数都与$n$互质，因此$p$也与$n$互质，即$p$存在于$A$中，那么剩下的数都可以选。

#include <iostream>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define met(a , b) memset(a , b , sizeof a);
#define pb push_back

using namespace std;

typedef long long LL ;
typedef pair<int , int> PII;

const int N = 100010 , mod = 1e9 + 7;

void solve()
{
    int n , t = 1 , res = 0;
    cin >> n;
    vector<int> st(n , false);
    for(int i = 1 ; i < n ; i++)
        if(__gcd(i , n) == 1)
        {
            t = (LL)t * i % n;
            st[i] = true;
            res++;
        }

    if(t != 1) st[t] = false , res--;
    cout << res << endl;
    for(int i = 1 ; i < n ; i++)
        if(st[i])
            cout << i << ' ';
}

int main()
{
    int T = 1;
    //cin >> T;
    for(int turn = 1 ; turn <= T ; turn++)
        solve();
}