阶
当 $r$ 是最小的实数使得 $a^r\equiv1(\mod m)$ 成立。
那么 $r$ 是模 $m$ 意义下，$a$ 的阶。记作：
原根
而如果 $r=\varphi
(m)$ 那么 $a$ 是模 $m$ 的一个原根。也就是说：
且 $x\in[1,\varphi(m)-1]$：$a^x\not=1(\mod m)$
为了熟悉原根。我们先做几个题：
$1$ 是模 $2$ 的原根。
求模 $3$ 的原根：
$2$ 是模 $3$ 的原根。
- 求模 $4$ 的原根：
$3$ 是模 $4$ 的原根。
（重申一下：等式中间的 $2$ 代表的是 $3$ 的 $2$ 次幂模 $4$ 等于 $1$。）
- 模 $5$ 的原根是 $2$：
（$2$ 的 $4$ 次幂模 $5$ 等于 $1$。）
- 求模 $8$ 的原根：
设 $a$ 是素数，有 $a^2\equiv 1(\mod 8)$，但是 $\delta_8(a)=1$ 或 $2 < \varphi(8)=4$ 所以，模 $8$ 没有原根。
注意：这里有一个性质：原根一定和模数互质（否则模的结果一定不为 $1$）。
原根性质
- 我们上面已经知道有些数是没有原根的，有原根的数：
其中 $p$ 是奇素数。只有这些数有原根。
一个数如果存在原根，那么它有 $\varphi(\varphi(n))$ 个原根。
素数一定有原根。
对于阶 $r$，$a^0,a^1,…,a^{r-1}$ 模 $n$ 两两不同余；当 $a$ 是原根时，$a_0,a_1,…,a^{\delta-1}$ 是模 $n$ 的简化剩余系；当 $n$ 是质数时，$a^0,a^1,…,a^{\delta-1}$ 对 $n$ 取模后对应为 ${1,2,…,n-1}$。
如果我们有了最小原根 $r$（$\delta_n(r)=\varphi(n)$），那么 $x\in[1,\varphi(n)],\gcd(x,\varphi(n))=1$，$r^x\mod n$ 都是 $n$ 的原根。
如何求最小原根？
暴力枚举，假设现在枚举到了 $k$，那么首先 $\gcd(k,n)=1$，然后对于每个 $x\mid \varphi(n)$，$k^x\not\equiv 1(\mod n)$。
那么在我们找完 $\varphi(n)$ 的所有质因子后，如果当前枚举的数可以对于所有的质因子 $p_i$ 满足：$k^{\frac{n}{p_i}}\not\equiv1(\mod n)$。那么 $k$ 就是一个原根。
如果我们刚刚是从小到大枚举的那么 $k$ 就是 $n$ 的最小原根。后面我们就直接枚举它的幂判断是否与 $\varphi(n)$ 互质就可以统计了。
如果 $x\equiv1(\mod n)$，那么 $x^2\equiv1(\mod n)$，其他次幂同理，但是在枚举次幂的同时，注意判断和 $\varphi(n)$ 互质。
而和 $\varphi(n)$ 互质的数共有 $\varphi(\varphi(n))$ 个，这也就是为什么一个数有原根，那么就有 $\varphi(\varphi(n))$ 个原根。
代码思路
读取所有询问（离线处理）。
线性筛素数，处理欧拉函数，标记有原根的数有哪些。
处理 $\varphi(n)$ 的质因数，标记所有和它不互质的数。
枚举最小原根。
统计原根，根据题目要求输出。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
long long r_r(){//快读
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=1e6+10;
int z_z[o_o];//存质数
int x_z;//质数个数下标
int p_i[o_o];//欧拉函数
bool b_b[o_o];//合数判断
int f_i[9];//分解每个数
int u_i[11],v_i[11];//读入信息
bool f_b[o_o];//标记当前数是否有原根
bool b_i[o_o];//标记是否是当前询问的数的欧拉函数的因子的倍数
bool o_i[o_o];//标记是否是结果
void yv(int n){
f_b[2]=f_b[4]=p_i[1]=1;
for(int i=2;i<=n;i++){//线筛
if(!b_b[i]){//没有舍去是质数
z_z[++x_z]=i;//记录质数
p_i[i]=i-1;//记录欧拉函数
}
for(int j=1;j<=x_z&&i*z_z[j]<=n;j++){//筛
b_b[i*z_z[j]]=1;//标记合数
if(i%z_z[j]==0){//已经有当前因子，直接退出
p_i[i*z_z[j]]=p_i[i]*z_z[j];//已经贡献过，直接乘
break;
}
p_i[i*z_z[j]]=p_i[i]*p_i[z_z[j]];//欧拉函数是奇性函数
}
}
for(int i=2;i<=x_z;i++){//标记所有有原根的实数
for(int j=1;1ll*j*z_z[i]<=n;j*=z_z[i])f_b[j*z_z[i]]=1;
for(int j=2;1ll*j*z_z[i]<=n;j*=z_z[i])f_b[j*z_z[i]]=1;
}
}
int k_m(int a,int b,int m_d){//快速幂
int r_s=1;
while(b){
if(b&1)r_s=1ll*r_s*a%m_d;
a=1ll*a*a%m_d;
b>>=1;
}
return r_s;
}
int main(){
int t=r_r(),m_x=0;
for(int i=1;i<=t;++i){//离线做法
u_i[i]=r_r();
v_i[i]=r_r();
m_x=max(m_x,u_i[i]);//记录最大值
}
yv(m_x);//预处理质数，欧拉函数，原根
for(int k_i=1;k_i<=t;++k_i){//处理每个询问
//获取当前询问的值
int n=u_i[k_i];
int d=v_i[k_i];
if(!f_b[n]){//没有原根
puts("0\n");
continue;
}
int k_k=p_i[n];//记录欧拉函数
int x_f=0;
for(int i=1;z_z[i]*z_z[i]<=k_k;i++){//分解质因数
if(!(k_k%z_z[i])){//可以整除
f_i[++x_f]=z_z[i];//记录质因子
while(!(k_k%z_z[i]))k_k/=z_z[i];//将当前质因子除干净
for(int k=z_z[i];k<=p_i[n];k+=z_z[i])b_i[k]=1;
//当前质因子范围内所有倍数标记（后面要保证互质）
}
}
if(k_k>1){//还一个大质因子
f_i[++x_f]=k_k;//记录
for(int k=k_k;k<=p_i[n];k+=k_k)b_i[k]=1;//标记
}
int x_i=0;//最小原根
while(++x_i){
while(k_m(x_i,p_i[n],n)!=1)x_i++;//枚举找原根
int x_x=1;
while(x_x<=x_f&&k_m(x_i,p_i[n]/f_i[x_x],n)!=1)x_x++;
if(x_x>x_f)break;//是原根
}
int t_i=1,s_m=0;
for(int i=1;i<=p_i[n];i++){//统计所有原根
t_i=1ll*t_i*x_i%n;//计算原根
if(!b_i[i])o_i[t_i]=1,s_m++;//和 n 的欧拉函数互质，统计结果
else b_i[i]=0;//不互质
}
printf("%d\n",s_m);//输出原根统计的结果
int o_t=0;//统计是第几个合法的数
for(int i=1;i<n;i++){
if(o_i[i]){//可以统计
o_t++;//累计
if(o_t==d){//达到要求
printf("%d ",i);//输出
o_t=0;//累计清空
}
o_i[i]=0;//清空标记
}
}
puts("");
}
return 0;
}
