P6091 【模板】原根 题解

· · 题解

作为一个刚刚学会原根求法顺便卡到最优解榜三的数论蒟蒻，来这里给跟我一样对着题解区的长篇大论一头雾水的朋友们指指路，分享一种 O(n) 且又好理解又好写的做法~

（前置知识：欧拉函数）

0. 原根是啥？有啥用？

引用一段典中典：

你说的对，但是感觉不如原根。原根是数论中一个非常重要的概念。设 g,n 是正整数，若 g 模 n 的阶等于 \varphi(n)，即当且仅当 i = \varphi(n) 时 g^i \equiv 1 \pmod n，则称 g 为 n 的一个原根。对于 0 < i \le \varphi(n)，g^i \bmod n 的结果两两不同。我现在每天用原根都能做 10^5 次数据规模 10^6 的 NTT，也就是现实生活中 10^{17} 次乘法运算，这便是原根给我的骄傲的资本。

至于“阶”的概念，理解成 \{a^i \bmod n\} 的“循环节”长度就好。最重要的还是加粗的性质，后面会用到。

1. 什么样的数有原根？

结论：2,4,p^k,2p^k，其中 p 为奇素数，k 为正整数。（1 不在本题需考虑的范围之内）

打个暴力就可以粗略地验证了，实在想看证明的话可以移步隔壁数竞大佬的题解

2. 怎么判断一个数是否为另一个数的原根？

首先肯定要满足 g^{\varphi(n)} \equiv 1 \pmod n，用快速幂判断即可。

而如何判断 \forall 0 < i < \varphi(n),g^i \neq 1 是否成立呢？若不成立，设 x 是满足 g^x \equiv 1 \pmod n 的最小正整数，则一定有 x \mid \varphi(n)（否则 g^{\varphi(n) \bmod x}=1，不满足 x 最小），设 \frac{\varphi(n)}{x}=kp（k 为正整数，p 为 n 的一个质因数），则 g^\frac{\varphi(n)}{p}=g^{kx}=(g^x)^k \equiv 1 \pmod n。因此我们无需对所有 i 进行检验，只需对 \varphi(n) 的每个质因数 p 检验 g^\frac{\varphi(n)}{p} \bmod n 是否等于 1 即可，时间复杂度 O(\sqrt n + \log^2 n)（前半部分为分解质因数，后半部分为对每个质因数做一次快速幂）。

3. 一个数的原根有多少个？

由裴蜀定理可知，a \perp m 是不定方程 ax \equiv k \pmod m 当 k 为任意小于 m 的非负整数时均有解的充要条件。把这个结论运用到指数上，我们就得到了：若 g 为 n 的原根，则 a \perp \varphi(n) 是 (g^a \bmod n) 为 n 的原根的充要条件，因此若 n 存在原根，则其原根数量为 \varphi(\varphi(n))。

4. 如何求出一个数的所有原根？

王元院士早在 1959 年就证明过，**若 $n$ 存在原根，则其最小原根的数量级约在 $O(n^\frac{1}{4})$ 以下**，于是我们从 $2$ 开始枚举（$1$ 显然不可能是大于 $2$ 的数的原根），用第 2 节中的方法逐一判断是否为原根即可找到最小原根 $g_1$，该部分的复杂度是亚线性的。 接着根据第 3 节，只要找出 $(0,\varphi(n))$ 间所有与 $\varphi(n)$ 互质的数 $a$，$\{g_1^a \bmod n\}$ 即为 $n$ 的所有原根，排序后输出即可。找出与 $\varphi(n)$ 互质的数其实不需要 $\gcd$，可以用线性筛解决，搭配计数排序，完美的 $O(n)$！ ### 5. 如何让代码更好写？ - 用 `__builtin_ctz` 获取 $n$ 二进制末尾 $0$ 的个数可以带来便利。 - $\varphi(n)$ 不必在分解过程中计算，代公式可知 $\varphi(n=p^k)=(p-1)p^{k-1}=\frac{(p-1)n}{p}$，$\varphi(n=2p^k)=(2-1)^{1-1}(p-1)p^{k-1}=\frac{(p-1)n}{2p}$，这时便可以利用前面求出的 $\operatorname{ctz}$ 来省去分类讨论的麻烦了。 - 用第 2 节中的方法判断是否为原根时，可使用 `std::any_of` 节省码量。 - 在线性筛的过程中用 `bitset` 标记原根，最后即可方便地使用 `count`、`_Find_first`、`_Find_next` 输出答案。 ### $\text{Code} 
#include <bits/extc++.h>

inline int qpow(long long a, int b, int mod) {
    long long res = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)
            res = res * a % mod;
    return res;
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        int n, d;
        std::cin >> n >> d;

        if (n == 2 || n == 4) {
            puts("1");
            if (d == 1)
                printf("%d", n - 1);
            putchar('\n');
            continue;
        }

        int num = n;
        int z = __builtin_ctz(num);
        if (z >= 2) {
            puts("0\n");
            continue;
        }
        num >>= z;

        // 对 n 分解质因数
        int k = 3;
        while (num % k && k * k <= num)
            k++;
        if (k * k > num)
            k = num;
        while (num % k == 0)
            num /= k;
        if (num != 1) {
            puts("0\n");
            continue;
        }

        // 对 phi(n) 分解质因数
        int phi = n / k * (k - 1) >> z;
        num = phi;
        std::vector<int> v;
        for (int i = 2; i * i <= num; i++)
            if (num % i == 0) {
                v.emplace_back(i);
                while (num % i == 0)
                    num /= i;
            }
        if (num != 1)
            v.emplace_back(num);

        // 查找最小原根
        int g = 2;
        while (qpow(g, phi, n) != 1 || std::any_of(v.begin(), v.end(), [&](int p) { return qpow(g, phi / p, n) == 1; }))
            g++;

        // 筛出与 phi(n) 互质的数，标记所有原根
        constexpr int N = 1e6;
        std::bitset<N> vis, ans;
        for (int i = 1, t = g; i < phi; i++, t = 1ll * t * g % n) {
            if (!vis[i])
                ans[t] = 1;
            for (int p : v) {
                if (1ll * i * p >= phi)
                    break;
                vis[i * p] = 1;
                if (i % p == 0)
                    break;
            }
        }

        // 输出答案
        printf("%d\n", ans.count());
        int i = ans._Find_first();
        for (int _ = d; --_;) // 这是重复 (d - 1) 次
            i = ans._Find_next(i);
        while (i != N) {
            printf("%d ", i);
            for (int _ = d; _--;) // 这是重复 d 次
                i = ans._Find_next(i);
        }
        putchar('\n');
    }
}