Visits: 400

数论中的一个小概念，也是 NTT 的基础。

阶

若 $\gcd(a,m) = 1$，使 $a^l \equiv 1 \pmod m$ 成立的最小正整数 $l$，称为 $a$ 关于模 $m$ 的阶，记为 $\text{ord}_m a$。

若 $\text{ord}_m a = l$，则 $\text{ord}_m a^t = \frac{l}{\gcd(t,l)}$。

若 $\text{ord}_m a = l$，则 $a^n \equiv 1 \pmod m$ 当且仅当 $l|n$，特别地，$l | \varphi(m)$。

原根

若 $\text{ord}_mg = \varphi(m)$，则称 $g$ 是 $m$ 的一个原根。

判断是否有原根

若 $m$ 有原根，则 $m$ 一定是 $2,4,p^a,2p^a$ 的形式，这里的 $p$ 为奇质数，$a$ 为正整数。

求所有原根

设 $g$ 为 $m$ 的一个原根，则对于 $s \in [1,\varphi(m)]$ 且 $\gcd(s, \varphi(m)) = 1$，$g^s$ 为 $m$ 的全部原根。因此，若 $m$ 有原根，则 $m$ 有 $\varphi(\varphi(m))$ 个原根。

求一个原根

若 $g$ 是 $m$ 的原根，当且仅当 $\gcd(g,m) = 1$，且对于 $\varphi(m)$ 的任意一个质因子 $p$，都有 $g^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod m$。

【模板】P6091 【模板】原根

int m, d, phi, qhi;
vector<pi> p, q;

inline void div(int n, vector<pi> &p, int &phi) {
    p.clear(), phi = n;
    for (int i = 2; i * i <= n; i++)
        if (!(n % i)) {
            phi = 1ll * phi * (i - 1) / i;
            p.pb(mp(i, 0));
            while (!(n % i)) ++p.back().se, n /= i;
        }
    if (n > 1) phi = 1ll * phi * (n - 1) / n, p.pb(mp(n, 1));
}

inline bool pd(int m) {
    if (m & 1) return p.size() == 1u;
    if (m == 2 || m == 4) return 1;
    return p.size() == 2u && p[0] == mp(2, 1);
}

inline int ksm(int a, int b, int m) {
    int c = 1 % m;
    while (b) {
        if (b & 1) c = 1ll * c * a % m;
        a = 1ll * a * a % m, b >>= 1;
    }
    return c;
}

inline bool chk(int g) {
    if (__gcd(g, m) > 1) return 0;
    for (pi o : q)
        if (ksm(g, phi / o.fi, m) == 1) return 0;
    return 1;
}

inline void solve() {
    rd(m), rd(d);
    div(m, p, phi);
    if (!pd(m)) return prints("0\n");
    div(phi, q, qhi);
    int g = 1;
    while (!chk(g)) ++g;
    print(qhi);
    vi ans;
    for (int i = 1, G = g; i <= phi; i++, G = 1ll * G * g % m) {
        if (__gcd(i, phi) > 1) continue;
        ans.pb(G);
    }
    sort(ans.begin(), ans.end());
    for (int i = 1; i <= qhi; i++)
        if (!(i % d)) print(ans[i-1], ' ');
    prints("");
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

参考资料

• OI Wiki 原根