首先给出阶的定义:$m>1$且$(a,m)=1$的情况下,使得$a^l\equiv 1(mod\ m)$的$l$最小值为$a$对模$m$的阶.

由欧拉定理,$a^{\phi(m)}\equiv1(mod\ m)$,则显然$l|\phi(m)$且$l\le \phi(m)$.

于是给出原根的定义:设$m$为正整数,$a$为整数,如果$a$对$m$的阶等于$\phi(m)$,那么称$a$为模$m$的一个原根.

原根的性质:

  • 一个正整数$m$有原根的充要条件是$m=2,4,p^e,2p^e$,其中$p$为奇素数,$e$为正整数.

  • 每个有原根的正整数$m$都有$\phi(\phi(m))$个原根

  • ${g,g^2,g^3,\cdots,g^{\phi(m)}}$构成模$m$的一个既约剩余系(指每个与模数互质的剩余系取一个出来形成的玩意)

    平常我们用的都是质数的原根,那么这时候这个既约剩余系就取遍了$1\sim m-1$.

于是我们得到了最直观的寻找原根的方法:可以从2开始枚举,判断它的$1 \sim \phi(m)-1$次方是否重复.由于原根大致出现在$m^{0.25}$左右,因此求解的复杂度大约是$O(m^{1.25})$.

然后考虑:据欧拉定理,若$(a,m)=1$,那么$a$的$\phi(m)$次方必定和$1$同余.显然若一个数和$m$不互质,一定不是原根.若互质且非原根,它的$n$次方的循环节必定是$\phi(m)$的约数.可以先列出$\phi(m)$的每个约数$d_k$,若一个数的$d_k$次与$1$同余则该数必定不是原根.

再考虑这种方法的优化:我们发现若$x^d\equiv 1(mod\ m)$,那么当$d’=2d,3d,\cdots(d’<\phi(m))$时,显然均有$x^{d’}\equiv 1(mod\ m)$.故我们不需要枚举所有约数,只需要枚举$\frac{m}{p_1},\frac{m}{p_2},\cdots,\frac{m}{p_k}$即可.因为如果其中任意一个的约数不符合就一定能通过该数检测出来.换句话说,他们涵盖了每个约数小于$\phi(m)$的倍数.

下面是洛谷模板题的代码,题面含义为:T组数据,每组给出n和d,求原根总数并每d个输出一个.忽略了部分常见函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int divisors[maxn],sdiv;
void getdivisor(int x)
{
sdiv=0;
for (int i=1;x>1&&i<=cnt;i++)
{
if (x%pri[i]==0)
{
divisors[++sdiv]=pri[i];
while (x%pri[i]==0) x/=pri[i];
}
}
}
bool check(int x,int y,int p){return pow(x,y,p)==1;}
int main()
{
read(T);
getphi(1000000);
while (T--)
{
read(n,d);
if (n!=2&&n!=4)
{
getdivisor(n);
if ((!(sdiv==1||(sdiv==2&&divisors[1]==2&&((n/2)&1))))||(divisors[1]==2&&sdiv==1))//这句应该可以更简便
{
puts("0\n");
continue;
}
}
else if (n==2)
{
puts("1");
puts(d==1?"1":"");
continue;
}
cout<<phi[phi[n]]<<endl;
getdivisor(phi[n]);
int minn=0;
rep(i,2,n-1)
{
bool flag=true;
if (gcd(i,n)!=1) flag=false;
if (sdiv>1) rep(j,1,sdiv) if (check(i,phi[n]/divisors[j],n))
{
flag=false;
break;
}
if (flag) {minn=i;break;}
}
int num=1;
ans[1]=minn;
for (int i=2,now=((LL)minn*minn)%n;now!=1;now=((LL)now*minn)%n,i++)
if (gcd(i,phi[n])==1) ans[++num]=now;
sort(ans+1,ans+num+1);
for (int i=d;i<=num;i+=d) cout<<ans[i]<<' ';
putchar('\n');
}
return 0;
}