V.阶与原根
实际上这部分内容在OI中应用很少，但它是一些重要思想以及算法的基础。
阶是在互质数 \((a,m)\) 间的定义：满足 \(a^n\equiv1\pmod m\) 的最小 \(n\) 被称作 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\)。
明显，在 \(a,m\) 不互质时，\(a\) 的无论多少次幂全都是 \(\gcd(a,m)\) 的倍数，故不可能取到 \(1\)；而当互质时，依据扩展欧拉定理，必有 \(a^{\varphi(m)}\equiv1\pmod m\)，但也不排除存在更小的 \(n\)。
阶有什么性质呢？
性质1.\(a^1,a^2,\dots,a^{\delta_a(m)}\) 模 \(m\) 两两不同余。
如果两个数 \(a^i,a^j\) 同余的话（不妨设 \(i<j\)），则 \(a^i\times(a^{j-i}-1)\equiv0\pmod m\)，而 \(a^i\not\equiv0\pmod m\)，故只有可能 \(a^{j-i}-1\equiv0\pmod m\)，即 \(a^{j-i}\equiv0\pmod m\)，而 \(j-i\) 一定是 \(<\delta_a(m)\) 的，故此时 \(\delta_a(m)\) 就不是最小的满足 \(a^n\equiv1\pmod m\) 的 \(n\) 了，与前提矛盾。
性质2.若 \(a^n\equiv1\pmod m\)，则 \(\delta_m(a)|n\)。
\(f(n)=a^n\bmod m\) 这个函数，依照性质1，其最短循环节是 \(\delta_m(a)\)。故所有模 \(m\) 余 \(1\) 的数一定只存在于 \(\delta_m(a)\) 倍数的位置。
一个数 \(g\) 被称作 \(m\) 的原根，当且仅当 \(\delta_m(g)=\varphi(m)\)。
显然，其前提条件是 \(\gcd(g,m)=1\)，不然 \(\delta_m(g)\) 不存在。
原根判定定理：\(g\) 是 \(m\) 的原根，当且仅当对于一切 \(\varphi(m)\) 的质因数 \(p\)，都有 \(g^{\varphi(m)/p}\not\equiv1\pmod m\)。
原根个数定理：若 \(m\) 有原根，则原根个数是 \(\varphi\Big(\varphi(m)\Big)\)。
原根存在定理：\(m\) 有原根，当且仅当 \(m\in\{2,4,p^\alpha,2p^\alpha\}\)，其中 \(p\) 是奇质数，\(\alpha\in\N^+\)。
最小原根级别定理：若 \(m\) 有原根，则最小原根是 \(\sqrt[4]{m}\) 级别的。
什么？你问证明？但是考试也不考证明啊（摊手）
原根寻找方法：暴力找到最小原根 \(g\)，则对于所有与 \(\varphi(m)\) 互质的 \(x\)，\(g^x\) 都是 \(m\) 的原根。
时间复杂度 \(O\Bigg(\log m\Big(\sqrt[4]{m}+\varphi\big(\varphi(m)\big)\Big)+\varphi(m)\Bigg)\)。
总结步骤：
- 判断 \(m\) 是否 \(\in\{2,4,p^\alpha,2p^\alpha\}\)，不是则直接返回。
- 预处理 \(\varphi(m)\) 所有质因数。
- 从小到大枚举与 \(m\) 互质的 \(i\)，并依次用快速幂检验 \(\varphi(m)\) 所有质因数。
- 找到最小原根，枚举所有与 \(\varphi(m)\) 互质的数，求快速幂即可。
V.I.【模板】原根
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int T,n,d,pri[1001000],phi[1001000],mnp[1001000];
int ksm(int x,int y){
int z=1;
for(;y;y>>=1,x=1ll*x*x%n)if(y&1)z=1ll*z*x%n;
return z;
}
void sieve(){
for(int i=2;i<=N;i++){
if(!pri[i])pri[++pri[0]]=i,phi[i]=i-1,mnp[i]=i;
for(int j=1;j<=pri[0]&&i*pri[j]<=N;j++){
pri[i*pri[j]]=true,mnp[i*pri[j]]=pri[j];
if(i%pri[j])phi[i*pri[j]]=phi[i]*phi[pri[j]];
else{phi[i*pri[j]]=phi[i]*pri[j];break;}
}
}
}
vector<int>factorize(int ip){
vector<int>ret;
while(ip!=1)ret.push_back(mnp[ip]),ip/=mnp[ip];
sort(ret.begin(),ret.end()),ret.resize(unique(ret.begin(),ret.end())-ret.begin());
return ret;
}
bool checkrootexist(int ip){
if(n==2||n==4)return true;
vector<int>v=factorize(ip);
if(v.size()==1&&v[0]!=2)return true;
if(ip&1)return false;
v=factorize(ip/2);
return v.size()==1&&v[0]!=2;
}
vector<int>fp;
bool checkisroot(int ip){
for(auto i:fp)if(ksm(ip,phi[n]/i)==1)return false;
return true;
}
vector<int>res;
void findallroots(int ip){
for(int i=1;i<=phi[n];i++)if(__gcd(i,phi[n])==1)res.push_back(ksm(ip,i));
sort(res.begin(),res.end());
}
int main(){
sieve();
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&d),res.clear();
if(!checkrootexist(n)){puts("0\n");continue;}
fp=factorize(phi[n]);
for(int i=1;;i++)if(__gcd(i,n)==1&&checkisroot(i)){findallroots(i);break;}
printf("%d\n",res.size());
for(int i=d-1;i<res.size();i+=d)printf("%d ",res[i]);puts("");
}
return 0;
}