让我们发扬类人智慧。

这是非正解做法，仅供参考。

考虑到以下定理：

若 $\gcd (a,m) = 1$, 则 $a ^ {\varphi(m)} \equiv 1 \pmod m$。

且对于 $m \not\in \{1,2\}$，$\varphi(m) \equiv 0 \pmod 2$。

所以我们把 $m=1$ 或 $m=2$ 特判掉。

剩下的 $m$，利用质因数分解，将 $\varphi(m)$ 求出来，然后我们随机枚举 $x$。

接下来判断 $x$ 是否与 $m$ 互质。

如果互质，则枚举将 $\varphi(m)$ 除以多少个 $2$（前提是当前还能被 $2$ 整除），可以使得 $x ^ {(\frac{\varphi(m)}{2^i} )^2} \equiv 1 \pmod m$，如果上面的式子成立便可以将 $x ^{(\frac{\varphi(m)}{2^i} )}$ 扔进一个 set 里。

最后一块将 set 里的东西输出。

加以卡时。（实测单个测试点 2ms 过不了 HACK。4 ms 能 AC 本题，但为了保底，赛场上使用了 900 ms，并且基本上卡不掉。同时还能抢到全场跑的最慢解。）

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int phi=1;
int m;
vector<int> p;
const int V = 1e5+10;
int ip[V];
long long qpow(int a,int b,int mod)
{
	int res=1;
	while(b)
	{
		if(b&1) res*=a,res%=mod;
		a*=a,a%=mod;b/=2;
	}
	return res;
}
random_device rd; 
mt19937 rnd(rd());
set<int> st;
double s;
signed main()
{
	s=clock();
	// cout<<s<<' ';
	cin>>m;
	for(int i=2;i<=V-10;i++)
	{
		if(ip[i]==0) p.push_back(i),ip[i]=i;
		for(auto j:p)
		{
			if(j>ip[i]||i*j>V-10) break;
			ip[i*j]=j;
		}
	}
	int tmp=m;
	for(auto i:p)
	{
		int cnt=0;
		while(tmp%i==0)
		{
			// cout<<i<<' ';
			if(cnt) phi*=i;
			else phi*=(i-1);
			tmp/=i;
			cnt++;
		}
	}
	if(tmp>1) phi*=(tmp-1);
	st.insert(1);
	// cout<<clock()<<' ';
	while(clock()-s<900000)
	{
		int p=rnd()%(m);
		int cnt=0;
		if(__gcd(p,m)>1) continue;
		int tmp=phi;
		while(qpow(p,tmp,m)==1&&!(tmp&1)) tmp/=2;
		int res=qpow(p,tmp,m);
		st.insert(res);
	}
	if(m==1)
	{
		cout<<"-1";
		return 0;
	}
	for(auto i:st) cout<<i<<'\n';
	return 0;
}

乘上与平时相反的列车，为了去见从未见过的风景。