#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int st[N];

int main( )
{

        int n;
        memset(st,0,sizeof(st));
        long long sum=1;
        cin>>n;
        for(int i=1;i<n;i++)
        {
            if(__gcd(i,n)==1)
            sum=sum*i%n,st[i]=1;
        }

        if(sum!=1)
            st[sum]=0;
        cout<<count(st+1,st+n+1,1)<<endl;
        for(int i=1;i<n;i++)
        if(st[i])
        cout<<i<<" ";
 } 

结论：选所有与n互质的数的乘积记为mul,记p=mul%n。（1）若p==1,则直接输出选中的数，（2）若p!=1,输出p之外的其他数。

证明：（1）为什么选所有与n互质的数呢？ 怎么想到的呢？（首先得知道和n不互质的数 %n 结果必大于1。）先来证明为什么是必大于1。 记某个不和n互质的数为x。（x< n就不考虑了）。x与n不互质。记g=gcd(x,n)，则有g>1。因为x%n == (x/g)%(n/g)*g， 因为g>1 ，所以结果必达于1。这就是为什么我们要选与n互质的数相乘,一旦有一个数与n不互质，那他们的乘积与n也就不互质了。

（2）那为什么p!=1就输出p之外的数呢？为什么p是在之前所选的数中的一个呢？ 先来看前面一个问题：

乘积为mul。mul%n=p即 mul=kn+p,左右两边同除以p，哦吼，这不就是 mul/p=k /p n+1,这不就是%n结果为1了吗？ 那又要发问了，你怎么知道p是在选中的数的其中一个呢？ 先来想想p是什么鬼东西，p是mul%n的值，所以 0<=p<=n-1。哦吼，这不就是题目给的原序列吗？只要p敢和n互质，我就敢肯定的说，你化成灰我都认识。再来看 因为gcd(mul,n)==gcd(mul%n,n)==1； 且 p=mul%n ； 所以gcd(p,n)==1,这下没跑了，认出p 的骨灰了。