题解
定义 (delta_m(a))（(a) 模 (m) 的阶）为满足 (a^nequiv 1pmod m) 的最小的正整数 (n)。
原根 (g) 就是满足 (delta_m(g)=varphi(m)) 的正整数。
一个数 (a) 是原根的充要条件是对于 (varphi(m)) 的任意素因子 (p)，都有 (a^{varphi(m)/p} otequiv1 pmod m)，且 (a^{varphi(m)}equiv 1 pmod m)。
一个关于原根的性质是，假如我们知道了模 (m) 意义下的最小原根 (g)，那么其它所有原根都形如 (g^{alpha})，其中 (alphaperp varphi(m))。由此也可以得出一个数 (m) 如果有原根，那么其原根个数为 (varphi(varphi(m)))。
另一方面我们也有原根存在定理：如果正整数 (m) 等于 (2,4,p^{alpha},2p^{alpha})（(p) 是奇质数），那么 (m) 有原根。
又有一个定理：如果一个数 (m) 有原根，那么其最小原根的大小不会超过 (m^{0.25})。
于是我们可以在 (O(m^{0.25}omega(m)log m)) 的时间复杂度内找到 (m) 的最小原根，并在 (O(varphi(m) log m)) 的时间复杂度内找到所有原根。
(omega(m)) 是 (m) 的不同质因子个数。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &x){
x=0;int _f=1;
char ch=getchar();
while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
x=x*_f;
}
template<typename T,typename... Args> void Read(T &x,Args& ...others){
Read(x);Read(others...);
}
typedef long long ll;
const int N=1e6+5;
int T;
int vis[N],prime[N],prCnt=0,phi[N],rt[N];
void Sieve(int mx){
phi[1]=vis[1]=1;
For(i,2,mx){
if(!vis[i]) prime[++prCnt]=i,phi[i]=i-1,rt[i]=1;
for(int j=1;j<=prCnt&&1LL*i*prime[j]<=mx;++j){
vis[i*prime[j]]=1;
if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
rt[2]=rt[4]=1;
for(int j=2;j<=prCnt;++j){
for(ll cur=prime[j];cur<=mx;cur*=prime[j]){
rt[cur]=1;
if(2*cur<=mx) rt[2*cur]=1;
}
}
}
ll Pow(ll a,ll b,ll p){
ll res=1;
while(b){
if(b&1) res=res*a%p;
b>>=1,a=a*a%p;
}return res;
}
bool Check(ll g,ll n,vector<int> &pfac){
for(int p:pfac){
if(Pow(g,phi[n]/p,n)==1) return 0;
}return Pow(g,phi[n],n)==1;
}
int main(){
Sieve(N-5);
Read(T);
int n,d;
while(T--){
Read(n,d);
if(!rt[n]){puts("0
");continue;}
vector<int> pfac;
for(int j=1,n_=phi[n];prime[j]<=n_;++j){
if(n_%prime[j]==0){
pfac.push_back(prime[j]);
while(n_%prime[j]==0) n_/=prime[j];
}
}
int g;
for(g=1;g<=n;++g){
if(Check(g,n,pfac)) break;
}
vector<int> ans;
For(k,1,n) if(__gcd(k,phi[n])==1) ans.push_back(Pow(g,k,n));
sort(ans.begin(),ans.end());
auto it=unique(ans.begin(),ans.end());
ans.erase(it,ans.end());
printf("%d
",static_cast<int>(ans.size()));
for(auto it=ans.begin();it!=ans.end();++it){
if((distance(ans.begin(),it)+1)%d==0)
printf("%d ",*it);
}
// for(auto x:ans) printf("%d ",x);
puts("");
}
return 0;
}