文件详细信息

下载本文件

本文件的大小为 2092 字节。

#include<algorithm>
#include<cstdio>
#include<vector>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
template<typename T>
T gcd(const T a,const T b){
	return b?gcd(b,a%b):a;
}
typedef long long ll;
ll qpow(ll a,int x,const ll P){
	ll ans=1;
	while(x){
		if(x&1)ans=ans*a%P;
		a=a*a%P;
		x>>=1;
	}
	return ans;
}
const int maxval=1000000,maxcnt=78498;
bool flag[maxval+1];
int p[maxcnt+1],cnt,phi[maxval+1],T,n,d,c,g;
std::vector<int>factor[maxval+1];
void init(const int n){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!flag[i]){
			p[++cnt]=i;
			phi[i]=i-1;
			factor[i].push_back(i);
		}
		for(int j=1,target;j<=cnt&&(target=i*p[j])<=n;j++){
			flag[target]=true;
			factor[target].assign(factor[i].begin(),factor[i].end());
			if(factor[target].back()!=p[j])factor[target].push_back(p[j]);
			const int tmp=i/p[j];
			if(i==tmp*p[j]){
				phi[target]=phi[i]*p[j];
				break;
			}else phi[target]=phi[i]*(p[j]-1);
		}
	}
}
bool judge(const int x){
	for(int i:factor[phi[n]])
		if(qpow(x,phi[n]/i,n)==1)
			return false;
	return true;
}
bool ok(int n){
	if(n==2||n==4)return true;
	if((n&1)==0)n>>=1;
	if((n&1)==0)return false;
	for(int j=2,tmp;j<=cnt&&p[j]*p[j]<=n;j++)
		if(p[j]*(tmp=n/p[j])==n){
			do n=tmp;
			while(p[j]*(tmp=n/p[j])==n);
			return n==1;
		}
	return true;
}
int ans[maxval+1],tot;
void solve(){
	read(n),read(d);
	if(ok(n)){
		c=phi[phi[n]];
		write(c),putchar('\n');
		if(d>c){
			putchar('\n');
			return;
		}
		g=1;
		while(gcd(g,n)>1||!judge(g))g++;
		tot=0;
		for(int i=1,cur=1;i<=phi[n];i++){
			cur=cur*g%n;
			if(gcd(phi[n],i)==1)ans[++tot]=cur;
		}
		std::sort(ans+1,ans+c+1);
		for(int i=d;i<=c;i+=d)write(ans[i]),putchar(i+d<=c?' ':'\n');
	}else putchar('0'),putchar('\n'),putchar('\n');
}
int main(){
	init(maxval);
	read(T);
	while(T--)solve();
	return 0;
}