首先给出阶的定义:$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;
}