原根

前置知识1：欧拉定理

• 若 $\gcd(a,m) =1$，则 $a^ { \phi(m) } \equiv 1\pmod m$

因此当 $\gcd(a,m) =1$ 时，存在一个最小正整数 $n$ 使得 $a^ { n } \equiv 1\pmod m$ ，这个 $n$ 称作 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$ 。

原根： 若 $\gcd(a,m) =1$ ，且 $\delta_m(a)=\phi(m)$ ，则称 $a$ 为模 $m$ 的原根。

阶的性质：

1. 若 $a^n \equiv 1 \pmod m$ ，则 $\delta_m(a)|n$ 。

• 证明：显然

2. 设 $\gcd(a,m)=\gcd(b,m)=1$ ，
   则 $\delta_m(ab)=\delta_m(a)\delta_m(b)$ 的充要条件是 $\gcd(\delta_m(a),\delta_m(b))=1$ 。

证明：

• 必要性：
  由 $a^ { \delta_m(a) } \equiv 1\pmod m$ 和 $b^ { \delta_m(b) } \equiv 1\pmod m$
  可知 $(ab)^ { { \rm lcm } (\delta_m(a),\delta_m(b)) } \equiv 1\pmod m$，
  故 $\delta_m(ab)| { \rm lcm } (\delta_m(a),\delta_m(b))$ 。
  又因为 $\delta_m(ab)=\delta_m(a)\delta_m(b)$ ，
  故 $\delta_m(a)\delta_m(b)| { \rm lcm } (\delta_m(a),\delta_m(b))$ ，
  即 $\gcd(\delta_m(a),\delta_m(b))=1$ 。

• 充分性：
  由 $(ab)^ { \delta_m(ab) } \equiv 1\pmod m$ 可知：
  $1\equiv (ab)^ { \delta_m(ab)\delta_m(b) } \equiv a^ { \delta_m(ab)\delta_m(b) } \times b^ { \delta_m(b)\delta_m(ab) } \equiv a^ { \delta_m(ab)\delta_m(b) } \pmod m$ 。
  故 $\delta_m(a)|\delta_m(ab)\delta_m(b)$ 。
  又因为 $\gcd(\delta_m(a),\delta_m(b))=1$ ，
  则 $\delta_m(a)|\delta_m(ab)$ 。
  同理，$\delta_m(b)|\delta_m(ab)$ 。
  又因为 $\gcd(\delta_m(a),\delta_m(b))=1$ ，
  故有 $\delta_m(a)\delta_m(b)|\delta_m(ab)$ 。
  另一方面， $(ab)^ { \delta_m(a)\delta_m(b) } =(a^ { \delta_m(a) } )^ { \delta_m(b) } \times (b^ { \delta_m(b) } )^ { \delta_m(a) } \equiv 1\pmod m$
  故 $\delta_m(ab)|\delta_m(a)\delta_m(b)$
  综上， $\delta_m(ab)=\delta_m(a)\delta_m(b)$

3.若 $\gcd(a,m)=1$ ，则 $\delta_m(a^k)=\frac { \delta_m(a) } { \gcd(\delta_m(a),k) }$

• 证明：
  $a^ { k\delta_m(a^k) } =(a^k)^ { \delta_m(a^k) } \equiv 1\pmod m$
  $\Rightarrow \delta_m(a)|k\delta_m(a^k)$
  $\Rightarrow \frac { \delta_m(a) } { \gcd(\delta_m(a),k) } |\delta_m(a^k)$
  另一方面，
  $(a^k)^ { \frac { \delta_m(a) } { \gcd(\delta_m(a),k) } } =(a^ { \delta_m(a) } )^ { \frac { k } { \gcd(\delta_m(a),k) } } \equiv 1\pmod m$
  $\Rightarrow \delta_m(a^k)| { \frac { \delta_m(a) } { \gcd(\delta_m(a),k) } }$
  综上，有 $\delta_m(a^k)=\frac { \delta_m(a) } { \gcd(\delta_m(a),k) }$

回到正题，我们来思考怎样的数有原根。
首先，易证 $m=1,2,4$ 时有原根。
结论一：奇质数有原根

• 证明：待补充

结论二：对于奇质数 $p$ ， $\alpha\in \mathbb { N } ^*$ ， $p^\alpha$ 有原根。

• 证明：待补充

结论三：对于奇质数 $p$ ， $\alpha\in\mathbb { N } ^*$ ， $2p^\alpha$ 有原根。

• 证明：待补充

结论四：对于 $m \in \{1,2,4\}$ 且不存在奇质数 $p$ 及 $\alpha\in\mathbb { N } ^*$ 使得 $m\in\{p^\alpha,2p^\alpha\}$ ，模 $m$ 的原根不存在。

• 证明：待补充

综上，仅 $1,2,4,p^\alpha,2p^\alpha$ ，其中 $p$ 为奇质数， $\alpha\in\mathbb { N } ^*$ 。

如何求一个数 $n$ 的所有原根？
首先找到 $n$ 的最小原根，记为 $g$ ，则 $n$ 的所有原根均可由 $g$ 乘方得到。
具体的，若 $n$ 有原根，必有 $\phi(\phi(n))$ 个原根，每个都形如 $g^k\mod n$ 的形式，要求满足 $\gcd(k,\phi(n))=1$ 。
于是，我们在求得 $n$ 的最小原根 $g$ 后便可 在 $O(\phi(n)\log\phi(n))$ 的时间内求得 $n$ 的所有原根。

---

如何求得 $n$ 的最小原根 $g$ ？
枚举即可。

• 王元于 1959 年证明了若 $n$ 有原根，其最小原根是不多 $n^ { 0.25 }$ 级别的。
  事实上，由大量试验数据可以发现，对于足够大的 $n$，其最小正原根的大小不是多项式级别的。
  ——百度百科

根据这个结论，我们可以从小到大枚举。由原根的定义，若 $g$ 为模 $n$ 的原根，则对于 $\phi(n)$ 的任意素因数 $p$，必有：
$g^ { \phi(n)/p } \not\equiv 1\pmod n$
并且，满足如上条件的 $g$ 必为 $n$ 的原根

我们可以预处理出 $\phi(n)$ 的所有质因数，快速幂来判断。

$\texttt { problem link: }$
Luogu P6091 【模板】原根

$\texttt { code }$

#include <bits/stdc++.h>
using namespace std;
int n, _, d, prime[100010], np[1000010], phi[1000010], tot, mx;
int ans[500010], cnt;
vector<int> f;
int qp(long long x, int k, int mod)  { 
    long long res = 1;
    while (k)  { 
        if (k & 1)
            res = (res * x) % mod;
        x = (x * x) % mod, k >>= 1;
     } 
    return res;
 } 
int gcd(int x, int y)  { 
    while (x) swap(x, y), x %= y;
    return y;
 } 
bool check(int t)  { 
    if (!(t & 3))
        return false;
    if (!(t & 1))
        t >>= 1;
    int x = np[t];
    while (np[t] == x) t /= x;
    return t == 1;
 } 
int main()  { 
    phi[1] = 1;
    for (int i = 2; i <= 1000000; i++)  { 
        if (!np[i])
            prime[++tot] = np[i] = i, phi[i] = i - 1;
        for (int j = 1; j <= np[i] && i * prime[j] <= 1000000; j++)  { 
            np[i * prime[j]] = prime[j];
            if (prime[j] == np[i])
                phi[i * prime[j]] = phi[i] * prime[j];
            else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
         } 
     } 
    scanf("%d", &_);
    while (_--)  { 
        scanf("%d%d", &n, &d);
        if (n == 2)  { 
            printf(d == 1 ? "1\n1\n" : "1\n\n");
            continue;
         } 
        if (n == 4)  { 
            printf(d == 1 ? "1\n3\n" : "1\n\n");
            continue;
         } 
        if (!check(n))  { 
            printf("0\n\n");
            continue;
         } 
        int k = phi[n], x;
        f.clear(), cnt = 0;
        while (k > 1)  { 
            x = np[k], f.push_back(phi[n] / x);
            while (np[k] == x) k /= x;
         } 
        for (int i = 1;; i++)  { 
            if (qp(i, phi[n], n) != 1)
                continue;
            bool flag = true;
            for (auto j : f)  { 
                if (qp(i, j, n) == 1)  { 
                    flag = false;
                    break;
                 } 
             } 
            if (flag)  { 
                ans[++cnt] = i;
                break;
             } 
         } 
        printf("%d\n", phi[phi[n]]);
        long long kk = ans[1];
        for (int i = 1; i < phi[n] - 1; i++)  { 
            kk = (kk * ans[1]) % n;
            if (gcd(i + 1, phi[n]) == 1)
                ans[++cnt] = kk;
         } 
        sort(ans + 1, ans + 1 + cnt);
        for (int i = d; i <= cnt; i += d) printf("%d ", ans[i]);
        putchar('\n');
     } 
    return 0;
 } 

实测将每次判 gcd(i + 1, phi[n]) == 1 改为预处理 $\phi(n)$ 质因数的倍数后，速度提升了数倍不止。
修改后的代码如下：
$\texttt { code }$

#include <bits/stdc++.h>
using namespace std;
int n, _, d, prime[100010], np[1000010], phi[1000010], tot, mx;
int ans[500010], cnt;
bool is[1000010], cant[1000010];
vector<int> f;
int qp(long long x, int k, int mod)  { 
    long long res = 1;
    while (k)  { 
        if (k & 1)
            res = (res * x) % mod;
        x = (x * x) % mod, k >>= 1;
     } 
    return res;
 } 
int gcd(int x, int y)  { 
    while (x) swap(x, y), x %= y;
    return y;
 } 
bool check(int t)  { 
    if (!(t & 3))
        return false;
    if (!(t & 1))
        t >>= 1;
    int x = np[t];
    while (np[t] == x) t /= x;
    return t == 1;
 } 
int main()  { 
    phi[1] = 1;
    for (int i = 2; i <= 1000000; i++)  { 
        if (!np[i])
            prime[++tot] = np[i] = i, phi[i] = i - 1;
        for (int j = 1; j <= np[i] && i * prime[j] <= 1000000; j++)  { 
            np[i * prime[j]] = prime[j];
            if (prime[j] == np[i])
                phi[i * prime[j]] = phi[i] * prime[j];
            else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
         } 
     } 
    scanf("%d", &_);
    while (_--)  { 
        scanf("%d%d", &n, &d);
        if (n == 2)  { 
            printf(d == 1 ? "1\n1\n" : "1\n\n");
            continue;
         } 
        if (n == 4)  { 
            printf(d == 1 ? "1\n3\n" : "1\n\n");
            continue;
         } 
        if (!check(n))  { 
            printf("0\n\n");
            continue;
         } 
        int k = phi[n], x;
        long long kk;
        f.clear(), cnt = 0;
        while (k > 1)  { 
            x = np[k], f.push_back(phi[n] / x);
            while (np[k] == x) k /= x;
            for (int i = x; i <= n; i += x) cant[i] = true;
         } 
        for (int i = 1;; i++)  { 
            if (qp(i, phi[n], n) != 1)
                continue;
            bool flag = true;
            for (auto j : f)  { 
                if (qp(i, j, n) == 1)  { 
                    flag = false;
                    break;
                 } 
             } 
            if (flag)  { 
                is[i] = true, kk = x = i;
                break;
             } 
         } 
        printf("%d\n", phi[phi[n]]);
        for (int i = 1; i < phi[n] - 1; i++)  { 
            kk = (kk * x) % n;
            if (!cant[i + 1])
                is[kk] = true;
         } 
        cnt = 0;
        for (int i = 1; i <= n; i++)  { 
            if (is[i])  { 
                is[i] = false;
                if (++cnt == d)
                    printf("%d ", i), cnt = 0;
             } 
            cant[i] = false;
         } 
        putchar('\n');
     } 
    return 0;
 } 

$\texttt { that's all. }$