阶与原根

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

题意：

给定整数 $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;
}