Luogu P6091 【模板】原根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
int cntp, p[MAXn + 10]; bool notp[MAXn + 10];
int ola[MAXn + 10];
void EvaOla(int n) {
    notp[1] = 1;
    ola[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (notp[i] == 0) {
            p[++cntp] = i;
            ola[i] = i - 1;
        }
        for (int j = 1, toppj = n / i; j <= cntp && p[j] <= toppj; ++j) {
            notp[i * p[j]] = 1;
            if (i % p[j]) {
                ola[i * p[j]] = ola[i] * (p[j] - 1);
            } else {
                ola[i * p[j]] = ola[i] * p[j];
                break;
            }
        }
    }
}

int cntpf, pf[MAXn + 10];
void EvaPf(int n) {
    cntpf = 0;
    int tmpn = n, sqrtn = sqrt(n);
    for (int i = 1; p[i] <= sqrtn; ++i) {
        if (tmpn % p[i] == 0) {
            pf[++cntpf] = p[i];
            while (tmpn % p[i] == 0) tmpn /= p[i];
        }
    }
    if (notp[tmpn] == 0) {
        pf[++cntpf] = tmpn;
    }
}

inline bool HavG(int mod) {
    if (mod == 2 || mod == 4) return 1;
    EvaPf(mod);
    if (cntpf == 1 && pf[1] != 2) {
        return 1;
    } else if (cntpf == 2 && (pf[1] == 2 || pf[2] == 2)) {
        if ((mod / 2) % 2) {
            return 1;
        }
    }
    return 0;
}
inline int CntG(int mod) {
    return ola[ola[mod]];
}
inline bool isG(int a, int mod) {
    if (gcd(a, mod) != 1) return 0;
    for (int i = 1; i <= cntpf; ++i) {
        if (power(a, ola[mod] / pf[i], mod) == 1) {
            return 0;
        }
    }
    return 1;
}
int cntg, g[MAXn + 10];
void EvaG(int mod) {
    cntg = 0;
    EvaPf(ola[mod]);
    int firg;
    for (int i = 1; i < mod; ++i) {
        if (isG(i, mod)) {
            firg = i;
            break;
        }
    }
    for (int i = 1; i <= ola[mod]; ++i) {
        if (gcd(i, ola[mod]) == 1) {
            g[++cntg] = power(firg, i, mod);
        }
    }
    sort(g + 1, g + 1 + cntg);
}

int n, d;

int T;
signed main() {
    EvaOla(MAXn);
    read(T);
    while (T--) {
        read(n, d);
        int tmpcntg;
        if (HavG(n) == 0) {
            tmpcntg = 0;
        } else {
            tmpcntg = CntG(n);
        }
        if (tmpcntg < d) {
            printf("%lld\n", tmpcntg);
            puts("");
        } else {
            EvaG(n);
            printf("%lld\n", cntg);
            for (int i = 1, topi = cntg / d; i <= topi; ++i) {
                printf("%lld ", g[i * d]);
            }
            puts("");
        }
    }
    return 0;
}