原根

阶

由欧拉定理可知，对于a \in \mathbb{Z}, m \in \mathbb{N^{*}}，若gcd(a, m)=1，则a^{ \phi(m) } \equiv 1(mod m)。因此满足a^n \equiv 1(modm)的最小正整数n存在，这个最小的n就称作a模m的阶，记作\delta_{m}(a)。
注意阶不一定就等于\phi(m)，也可能是它的约数。
大脑里构想这玩意的时候，一定要和m的欧拉函数\phi(m)及其约数联系起来。

性质
1.a,a^1,a^2···a^{ \delta_m (a) }模m两两不同。这很好想，每一阶就是一个循环。
2.若a^{ n } \equiv 1(modm)，则\delta_{m}(a) | n。
3.对a,b \in \mathbb{Z}, m \in \mathbb{N^{*}}，若gcd(a,m)=gcd(b,m)=1，则\delta(ab)=\delta(a)\delta(b) \Leftrightarrow gcd(\delta(a),\delta(b))=1。
4.设k \in \mathbb{N}, m \in \mathbb{N^*},a \in \mathbb{Z}, gcd(a,m)=1，则\delta_m(a^k)= \frac{ \delta_m(a) }{ gcd(\delta_m(a), k) }。利用这一性质快速求所有原根。

原根

设a \in \mathbb{Z}, m \in \mathbb{N^{*}}，若gcd(a, m)=1且\delta_{m}(a)=\phi(m)，则a是m的一个原根。

根据上面阶的定义，那么判断a是否为m的一个原根，只要判断和\phi(m)的所有(除去1和它自身)的约数x是否满足a^x \equiv 1(modm)即可，若都不满足，则a是m的一个原根。

一个数m存在原根当且仅当m=2,4,p^{\alpha}, 2p^{\alpha},p为大于2的质数, \alpha \in \mathbb{N^*}。且m的原根个数为\phi( \phi(m) )。
若m存在原根，则其最小原根是不多于m^{0.25}级别的。可以暴力寻找m的第一个原根。

快速求所有原根

条件仍为上述条件，首先需要特判2和4，以及m是否有原根。确定m有原根之后，然后求出m最小的原根a。枚举\phi(m)的所有(不为1和它本身)约数x，若都不满足a^x \equiv 1(modm)，则a就是最小的原根。
然后再枚举[1,\phi(m)]中和\phi(i)互质的那些数k(包括1)，每一个a^k都是一个原根。那么总共有\phi( \phi(m) )个原根。

对于上述步骤的第二部分，证明为：利用上述阶部分的性质4，若已求得最小原根a，k满足gcd( \phi(m),k )=1，则有\delta_m (a^k) = \delta_m(a) = \phi(m)，那么a^k也是m的一个原根。

P6091 【模板】原根

T组数据，每次输入n，d，求n的所有原根，输出原根个数，每d个输出一个。

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn = 1e2+5;

int m, d;
int prime[maxn], cnt, phi[maxn];
bool vis[maxn];

int q[maxn], cnt2;
int A[maxn];

void init() {
    int n = maxn-5;
    phi[1] = 1;
    for (int i=2; i<=n; i++) {
        if (!vis[i])    prime[++cnt] = i, phi[i] = i-1;
        for (int j=1; j<=cnt && i*prime[j]<=n; j++) {
            vis[i*prime[j]] = 1;
            if (i%prime[j]==0) {
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i*prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    //for (int i=1; i<=n; i++)    vis[i] = 0;
    return;
}

inline ll pow_mod(ll a, ll b, const ll &mod) {
    if (0==a)   return 0;
    ll ans = 1;
    while ( b )
    {
        if (b&1)    ans = ans*a%mod;
        b >>= 1;
        a = a*a%mod;
    }
    return ans;
}

int gcd(int a, int b) {
    return b==0? a:gcd(b, a%b);
}

int main() {
    int t;
    scanf ("%d", &t);
    init();
    while (t--) {
        scanf ("%d %d", &m, &d);
        if (m!=2 && m!=4) {
            int tmp = m;
            if (tmp%2==0) tmp /= 2;
            if (tmp==1 || tmp%2==0) {
                puts("0\n");
                continue;
            }
            for (int i=2; i<=cnt; i++) if (tmp%prime[i]==0){
                while (tmp%prime[i]==0) tmp /= prime[i];
                break;
            }
            if (tmp!=1) {
                puts("0\n");
                continue;
            }
        }
        int tmp = phi[m], a;
        cnt2 = 0;
        for (int i=1; i<=tmp; i++) if (tmp%i==0){
            q[++cnt2] = i;
        }
        for (int i=2; i<tmp; i++) if (gcd(i,m)==1){
            bool flag = true;
            for (int j=2; j<cnt2; j++) if ( pow_mod(i, q[j], m)==1 ){
                flag = false;
                break;
            }
            if (flag) {
                a = i;
                break;
            }
        }
        int ans = 0;
        printf ("%d\n", phi[tmp]);
        if (m==2 || m==4) {
            A[++ans] = m-1;
        }else {
            A[++ans] = a;
            for (int i=2; i<tmp; i++) if ( gcd(i,tmp)==1 ) {
                A[++ans] = pow_mod(a, i, m);
            }
        }
        sort (A+1, A+ans+1);
        for (int i=d; i<=ans; i+=d) {
            printf ("%d", A[i]);
            if (i+d<=ans) putchar(' ');
        }
        if (t)  putchar('\n');
    }
    return 0;
}