阶与原根

前置知识：欧拉定理、费马小定理、拉格朗日定理。

题意：

给定整数 \(n\)，求它的所有原根。

为了减小你的输出量，给出输出参数 \(d\)，设 \(n\) 的所有原根有 \(c\) 个，从小到大分别为 \(g_1,\ldots,g_c\)，你只需要依次输出 \(g_d,g_{2d},\ldots,g_{\lfloor\frac{c}{d}\rfloor\times d}\)。

正整数 \(g\) 是正整数 \(n\) 的原根，当且仅当 \(1\leq g\leq n-1\)，且 \(g\) 模 \(n\) 的阶为 \(\varphi(n)\)。

输入格式：

本题包含多组数据。

第一行：一个整数 \(T\)，表示数据组数。

接下来 \(T\) 行：每行两个整数 \(n,d\)，表示一组询问数据。

输出格式：

对于每组数据：

第一行输出一个整数 \(c\)，表示 \(n\) 的原根个数，第二行输出 \(\lfloor\dfrac{c}{d}\rfloor\) 个数，按照题目描述中要求输出。

注意：即使 \(\lfloor\dfrac{c}{d}\rfloor=0\)，也需要输出一个空行。

数据范围：

对于 \(100\%\) 的数据，\(1\leq T\leq 10\)，\(2\leq n\leq 10^6\)，\(1\leq d\leq 200\)，保证输出的数的总个数不超过 \(10^5\)。

先放模板题是因为这篇文章是模板题题解，不过我们需要先了解什么是阶，什么又是原根。

阶：由欧拉定理可知，对于整数 \(a\) 和正整数 \(m\) ，若 \(\gcd(a,m)=1\) ，则 \[ a^{\varphi(m)} \equiv 1 \pmod{m} \] 因此满足同余式 \(a^n \equiv 1 \pmod{m}\) 的最小正整数 \(n\) 存在，这个 \(n\) 称作 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\)

原根：对于整数 \(a\) 和正整数 \(m\) ，若 \(\gcd(a,m)=1\) 且 \(\delta_m(a) = \varphi(m)\) ，则称 \(a\) 为模 \(m\) 的原根。

这里可能有一点点绕，大概就是定义了什么是阶，然后定义模 \(m\) 的阶为 \(\varphi(m)\) 的整数 \(a\) 为「模 \(m\) 的原根」。

关于阶有一个较为显然的性质：

性质1：若 \(a^n \equiv 1 \pmod{m}\) ，则 \(\delta_m(a) \mid n\) 。（注意这里 \(n\) 和之前不一样）

证明：对 \(n\) 除以 \(\delta_m(a)\) 作带余除法，设 \[ n = \delta_m(a)\cdot q + r\quad(0 \le r < \delta_m(a)) \] 若 \(r > 0\) ，则 \[ a^r \equiv a^r(a^{\delta_m(a)})^q \equiv a^n \equiv 1 \pmod{m} \] 这与 \(\delta_m(a)\) 的最小性矛盾。证毕。

除此以外，阶还有两个比较重要的性质。

性质2：对于整数 \(a,b\) 和正整数 \(m\) ，\(\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)^{\mathrm{lcm}(\delta_m(a),\delta_m(b))} \equiv 1 \pmod{m} \] 根据性质1，有 \[ \delta_m(a b) \mid \operatorname{lcm}\left(\delta_m(a), \delta_m(b)\right) \] 又由于 \(\delta_m(ab) = \delta_m(a)\delta_m(b)\) ，则 \[ \delta_m(a) \delta_m(b) \mid \operatorname{lcm}\left(\delta_m(a), \delta_m(b)\right) \] 即 \(\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)} \pmod m \] 故 \(\delta_m(a) \mid \delta_{m}(ab)\delta(b)\) 。结合 \(\gcd(\delta_m(a),\delta_m(b)) = 1\) ，得 \[ \delta_m(a) \mid \delta_m(ab) \] 同理可得 \[ \delta_m(b) \mid \delta_m(ab) \] 所以 \[ \delta_m(a) \delta_m(b) \mid \delta_m(a b) \] 另一方面，有 \[ (a b)^{\delta_m(a) \delta_m(b)} \equiv\left(a^{\delta_m(a)}\right)^{\delta_m(b)} \times\left(b^{\delta_m(b)}\right)^{\delta_m(a)} \equiv 1 \pmod m \] 故 \[ \delta_m(a b) \mid \delta_m(a) \delta_m(b) \] 综上可得 \[ \delta_m(a b)=\delta_m(a) \delta_m(b) \]

证毕。

性质3：设 \(k \in \mathbb{N}\) ，对于整数 \(a\) 和正整数 \(m\) ，\(\gcd(a,m) = 1\) ，则 \[ \delta_m(a^k) = \frac{\delta_m(a)}{\gcd(\delta_m(a),k)} \]

证明：注意到 \[ a^{k \delta_m\left(a^k\right)}=\left(a^k\right)^{\delta_m\left(a^k\right)} \equiv 1 \pmod m \] 则 \[ \delta_m(a) \mid k \delta_m\left(a^k\right) \] 即 \[ \frac{\delta_m(a)}{\operatorname{gcd}\left(\delta_m(a), k\right)} \mid \delta_m\left(a^k\right) \] 另一方面，由 \(a^{\delta_m(a)} \equiv 1\pmod m\) 可知 \[ \left(a^k\right)^{\frac{\delta_m(a)}{\operatorname{gcd}\left(\delta_m(a), k\right)}}=\left(a^{\delta_m(a)}\right)^{\frac{k}{\operatorname{gcd}\left(\delta_m(a), k\right)}} \equiv 1 \pmod m \] 故 \[ \delta_m(a^k) \mid \frac{\delta_m(a)}{\gcd(\delta_m(a),k)} \] 综上可得 \[ \delta_m(a^k) = \frac{\delta_m(a)}{\gcd(\delta_m(a),k)} \] 证毕。

至此我们知道了阶重要的性质，接着我们来说明怎样的 \(m\) 存在原根。

首先，显然 \(m=1,2,4\) 时原根存在。

定理1：对于奇素数 \(p\) ，\(p\) 有原根。

证明：

先证明一个引理：

引理：设 \(a\) 与 \(b\) 是与 \(p\) 互质的两个整数，则存在整数 \(c\) 使得 \(\delta_p(c) = \mathrm{lcm}(\delta_p(a),\delta_p(b))\)

证明：记 \(r = \delta_p(a),t = \delta_p(b)\) ，设他们的标准分解（这里对指数仅要求 \(\max(\alpha_j,\beta_j) > 0\)）分别为 \[ r=\prod_{j=1}^s p_j^{\alpha_j}, \quad t=\prod_{j=1}^s p_j^{\beta_j} \] 令 \(l\) 为所有 \(\alpha_j \le \beta_j\) 的 \(p_j^{\alpha_j}\) 的乘积，\(m\) 为所有 \(\alpha_j>\beta_j\) 的 \(p_j^{\alpha_j}\) 的乘积。

记 \(r = lx, t = my\) ，则这样定义的 \(x,y\) 满足 \(\gcd(x,y)=1\) 且 \(\mathrm{lcm}(r,t) = xy\) 。

由性质3，\(\delta_p(a^l) = x, \delta_p(b^m)=y\) ，由性质2，\(\delta_p(a^lb^m) = xy = \mathrm{lcm}(\delta_p(a),\delta_p(b))\) ，即 \(c=a^lb^m\) 。\(\square\)

考虑原命题，对 \(1\) 到 \((p-1)\) 依次两两使用引理，可知存在整数 \(g\) 使得 \[ \delta_p(g)=\operatorname{lcm}\left(\delta_p(1), \delta_p(2), \cdots, \delta_p(p-1)\right) \] 这表明 \(\delta_p(j) \mid \delta_p(g)\) 对于 \(j = 1,2,\cdots,p-1\) ，所以 \(j = 1,2,\cdots,p-1\) 都是同余方程 \[ x^{\delta_p(g)} \equiv 1 \pmod{p} \] 的根。由拉格朗日定理，可知方程的次数 \(\delta_p(g) \ge p - 1\)

由费马小定理，\(\delta_p(g) \le p-1\) ，故 \(\delta_p(g) = p-1 = \varphi(p)\) 。综上可知 \(g\) 为模 \(p\) 的原根。\(\square\)

定理2：对于奇素数 \(p\) ，设 \(\alpha \in \mathbb{Z_+}\) ，则 \(p^{\alpha}\) 有原根

证明：

先证明一个引理

引理：存在模 \(p\) 的原根 \(g\) ，使得 \(g^{p-1}\not\equiv 1\pmod{p^2}\)

证明：实际上，任取模 \(p\) 的原根 \(g\) ，若 \(g\) 不满足条件，我们认定 \(g+p\) 满足条件 \[ \begin{aligned} (g+p)^{p-1} & \equiv \binom{p-1}{0} g^{p-1}+\binom{p-1}{1} p g^{p-2} \\[6pt] & \equiv g^{p-1}+p(p-1) g^{p-2} \\[6pt] & \equiv 1-p g^{p-2} \\[6pt] & \not \equiv 1 \quad\pmod {p^2} \end{aligned} \] 证毕。

考虑原命题，我们证明若 \(g\) 是满足引理条件的原根，则对任意正整数 \(\alpha\) ，\(g\) 是模 \(p^{\alpha}\) 的原根。

首先证明下面的结论：对任意正整数 \(\beta\) ，都可设 \[ g^{\varphi(p^{\beta})} = 1 + p^{\beta} \times k_{\beta}\quad(p \not\mid k_{\beta}) \] 当 \(\beta = 1\) 时，由 \(g\) 的选取可知结论成立。现设上式对 \(\beta\) 时成立，则 \[ \begin{aligned} g^{\varphi\left(p^{\beta+1}\right)} & =\left(g^{\varphi\left(p^\beta\right)}\right)^p \\[6pt] & =\left(1+p^\beta \times k_\beta\right)^p \\[6pt] & \equiv 1+p^{\beta+1} \times k_\beta \pmod{p^{\beta+2}} \end{aligned} \] 结合 \(p \not\mid k_{\beta}\) 可知命题对 \(\beta+1\) 成立。所以命题对任意正整数 \(\beta\) 都成立。

其次，记 \(\delta = \delta_{p^{\alpha}}(g)\) ，则由欧拉定理可知 \(\delta \mid p^{\alpha - 1}(p - 1)\) 。

而由 \(g\) 为模 \(p\) 的原根，及 \(g^{\delta} \equiv 1\pmod{p^{\alpha}}\) 可知 \((p-1) \mid \delta\)

所以可设 \(\delta = p^{\beta - 1}(p-1)\) ，这里 \(1 \le \beta \le \alpha\) 。

利用之前的结论，可知 \[ g^{\varphi\left(p^\beta\right)} \not \equiv 1 \quad\pmod{p^{\beta+1}} \\[6pt]\Rightarrow g^\delta \not \equiv 1 \quad\pmod{p^{\beta+1}} \] 结合 \(g^{\delta}\equiv 1 \pmod{p^{\alpha}}\) 可知 \(\beta \ge \alpha\) 。综上可知 \(\beta = \alpha\) ，即 \[ \delta_{p^\alpha}(g)=p^{\alpha-1}(p-1)=\varphi\left(p^\alpha\right) \] 从而 \(g\) 是模 \(p\) 的原根。

定理3：对于奇素数 \(p\) ，设正整数 \(\alpha\) ，\(2p^{\alpha}\) 的原根存在。

证明：设 \(g\) 是模 \(p^{\alpha}\) 的原根，则 \(g + p^{\alpha}\) 也是模 \(p^{\alpha}\) 的原根。

在 \(g\) 和 \(g+p^{\alpha}\) 中有一个奇数，设这个奇数是 \(G\) ，则 \(\gcd(G,2p^{\alpha}) = 1\)

由欧拉定理，\(\delta_{2p^{\alpha}}(G) \mid \varphi(2p^{\alpha})\) ，而 \(G^{\delta_{2p^\alpha}(G)}\equiv 1 \pmod{2p^{\alpha}}\) ，故 \[ G^{\delta_{2p^\alpha}(G)}\equiv 1 \pmod{p^{\alpha}} \] 利用 \(G\) 为模 \(p^{\alpha}\) 的原根可知 \(G\) 为模 \(2p^{\alpha}\) 的原根。证毕。

定理4：对于 \(m \not\in \{1,2,4\}\) ，且不存在奇素数 \(p\) 及 \(\alpha \in \mathbb{Z}_+\) 使得 \(m \in \{p^{\alpha},2p^{\alpha}\}\) ，

则对任意整数 \(a\) 满足 \(\gcd(a,m)=1\) 都有 \(\delta_m(a) < \varphi(m)\) ，即模 \(m\) 的原根不存在。

证明：对于 \(m = 2^{\alpha}\) ，其中 \(\alpha \ge 3\,\land\,\alpha \in \mathbb{Z}_+\) ，则对任意奇数 \(a = 2k + 1\) 均有 \[ \begin{aligned} a^{2^{\alpha-2}} & =(2 k+1)^{2^{\alpha-2}} \\ & \equiv 1+C_{2^{\alpha-2}}^1(2 k)+C_{2^{\alpha-2}}^2(2 k)^2 \\ & \equiv 1+2^{\alpha-1} k+2^{\alpha-1}\left(2^{\alpha-2}-1\right) k^2 \\ & \equiv 1+2^{\alpha-1}\left(k+\left(2^{\alpha-2}-1\right) k\right) \\ & \equiv 1 \quad \pmod{2^\alpha} \end{aligned} \] 其中最后一步用到 \(k\) 与 \((2^{\alpha - 2} - 1)\cdot k\) 同奇偶的性质，故其和为偶数。

若 \(m\) 不是 \(2\) 的幂，且 \(m\) 为符合命题条件的数，则可设 \(m = rt\) ，这里 \(2 < r < t\) 且 \(\gcd(r,t)=1\) 。

此时，若 \(\gcd(a,m)=1\) ，由欧拉定理可知 \[ a^{\varphi(r)}\equiv 1 \pmod{r},~a^{\varphi(t)} \equiv 1 \pmod{t} \] 注意到 \(n > 2\) 时，\(\varphi(n)\) 为偶数，所以 \[ a^{\frac{1}{2} \varphi(r) \varphi(t)} \equiv 1 \pmod{rt} \] 进而 \[ \delta_m(a) \leq \frac{1}{2} \varphi(r) \varphi(t)=\frac{1}{2} \varphi(r t)=\frac{1}{2} \varphi(m)<\varphi(m) \] 证毕。

好好好，我们终于证明完了这些性质，总结一下对本题有用的结论是：

仅有 \(1,2,4\) 或奇素数 \(p^{\alpha}\) 及 \(2p^{\alpha}\) 有原根，其他的数都没有原根。

考虑预处理素数及其幂次，以及幂次 \(\times 2\) ，接着就可以 \(\mathcal{O}(1)\) 判断一个数有没有原根。

如果一个数有原根，可以先求出最小正原根，而正整数 \(m\) 的最小正原根的级别不超过 \(\mathcal{O}(m^{\frac{1}{4}})\)

因此考虑从小到大枚举。由原根的定义，若 \(g\) 为模 \(m\) 的原根，则对于 \(\varphi(m)\) 的任意素因数 \(p\) ，必有 \[ g^{\varphi(m) / p} \not \equiv 1 \pmod{m} \] 而满足以上条件的 \(g\) 必将是原根。考虑预处理出 \(\varphi(m)\) 的所有素因数，然后快速幂暴力判断

假如找到了一个原根 \(g\) ，不难证明对于所有 \(\gcd(x,\varphi(m)) = 1\) 的 \(x\) ，\(g^x\) 均为原根，

因此模 \(m\) 的原根有 \(\varphi(\varphi(m))\) 个，于是我们可以在找到 \(g\) 后枚举找出 \(m\) 的所有原根。

时间复杂度 \(\mathcal{O}(n^{\frac{1}{4}}\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

int tot,p[N],ck[N];
int _,num,cnt,phi[N],rt[N],fc[N],ans[N];
int gcd(int a,int b) { return b == 0 ? a : gcd(b, a % b); }
int qpow(int a, int b, int p){
    int r = 1;
    while(b) { if(b & 1) r = r * a % p; b >>= 1; a = a * a % p; }
    return r;
}
void init()
{
    phi[1] = 1;
    for(int i = 2; i <= 1e6 + 5; i++)
    {
        if(!ck[i]) { p[++tot] = i; phi[i] = i - 1; }
        for(int j = 1; j <= tot && i * p[j] <= 1e6 + 5; j++)
        {
            int pos = i * p[j]; ck[pos] = 1;
            if(i % p[j]) {
                phi[pos] = phi[i] * phi[p[j]];
            }else {
                phi[pos] = phi[i] * p[j]; break;
            }
        }
    }
    rt[2] = rt[4] = 1;
    for(int i = 2; i <= tot; i++)
    {
        for(int j = 1; p[i] * j <= 1e6 + 5; j *= p[i]) { rt[p[i] * j] = 1; }
        for(int j = 2; p[i] * j <= 1e6 + 5; j *= p[i]) { rt[p[i] * j] = 1; }
    }
}
bool check(int x, int p)
{
    if(qpow(x, phi[p], p) != 1) return false;
    for(int i = 1; i <= cnt; i++)
        if(qpow(x, phi[p] / fc[i], p) == 1) return false;
    return true;
}
int findrt(int p)
{
    for(int i = 1; i < p; i++)
        if(check(i, p)) return i;
    return 0;
}
void getrt(int p, int x)
{
    int tmp = 1;
    for(int i = 1; i <= phi[p]; i++)
    {
        tmp = tmp * x % p;
        if(gcd(i, phi[p]) == 1) ans[++num] = tmp;
    }
    return;
}
void solve()
{
    int p; cin >> p >> _; num = cnt = 0;
    if(!rt[p]) return cout << "0\n\n", void(0);
    int tmp = phi[p];
    for(int i = 2; i * i <= tmp; i++)
        if(tmp % i ==0) { 
            fc[++cnt] = i;
            while(tmp % i == 0) { tmp /= i; }
        }
    if(tmp > 1) fc[++cnt] = tmp;
    int mn = findrt(p); getrt(p, mn);
    sort(ans + 1, ans + 1 + num); cout << num << '\n';
    for(int i = 1; i <= num / _; i++) cout << ans[i * _] << ' ';
    cout << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    init(); int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}