盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 4992 Primitive Roots(求一个数的所有原根)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4992

题意

给定一个数n,求n的所有原根,按照从小到大输出,如果没有原根输出-1

思路

原根的定义:g^d % p = 1 其中d最小为phi(p),则g便为一个原根

  1. 一个数是否有原根
    判断数是否有原根:模n有原根的充要条件是n = 1,2,4,p,2p,p^q,其中p是奇质数,q是任意正整数。

  2. 若有,找其最小原根
    然后用欧拉公式求出n的m=φ(n),从2~n-1遍历找出n的最小原根a:判断a^m % n==1 是否成立
    计算出所有m的因子(1和m除外)y,若a^y % n==1,则a不可能是n的原根。因为存在性质:如果正整数gcd(a,m) = 1,正整数 d 满足a^d≡1(mod m),则 d 整除 φ(m)。

  3. 已知一个原根,得到所有原根
    得到所有a^x % n {2<=x<m,gcd(x,m)==1}的值为n的原根
    证明:http://blog.csdn.net/solotzg/article/details/39205337

代码

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
109
110
111
112
113
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
#define maxn 1000000
int ans[maxn + 10], valid[maxn + 10], tot = 0;
void getPrime(int n, int &tot, int ans[]) {
for (int i = 2; i <= n; i++) {
if (!valid[i]) ans[tot++] = i;
for (int j = 0; j < tot && i * ans[j] <= n; j++) {
valid[i * ans[j]] = 1;
if (i % ans[j] == 0) break;
}
}
}
///判断是否有原根
///判断数是否有原根:模n有原根的充要条件是n = 1,2,4,p,2p,p^q,其中p是奇质数,q是任意正整数。
bool has_primitive_root(int n) {
if (n % 2 == 0) n /= 2;
if (n % 2 == 0) return false;
for (int i = 1; ans[i] * ans[i] <= n; i++) if (n % ans[i] == 0){
while(n % ans[i] == 0) n /= ans[i];
if (n != 1) return false;
return true;
}
return true;
}
///得到最小的原根
ll pow_mod(ll a, ll x, ll p) {
ll res = 1;
while(x) {
if (x & 1) res = res * a % p;
x >>= 1;
a = a * a % p;
}
return res;
}
ll euler(ll x) {
ll res = x;
for (ll i = 0; ans[i] * ans[i] <= x; i++) if (x % ans[i] == 0) {
res = res / ans[i] * (ans[i] - 1);
while(x % ans[i] == 0) x /= ans[i];
}
if (x > 1) res = res / x * (x - 1);
return res;
}
vector<ll> a;
bool g_test(ll g, ll p, ll fhi_n) {
for (ll i = 0; i < a.size(); i++)
if (pow_mod(g, fhi_n / a[i], p) == 1) return 0;
return 1;
}
ll primitive_root(ll p, ll fhi_n) {
a.clear();
ll tmp = fhi_n;
for (ll i = 0; ans[i] * ans[i] <= tmp; i++) if (tmp % ans[i] == 0) { //这里还可以用筛素数优化
a.push_back(ans[i]);
while(tmp % ans[i] == 0) tmp /= ans[i];
}
if (tmp != 1) a.push_back(tmp);
ll g = 1;
while(true) {
if (pow_mod(g, fhi_n, p) != 1) { ///要先判断g^fhi_n % p == 1
g++;
continue;
}
if (g_test(g, p, fhi_n)) return g;
g++;
}
}
///根据最小原根得到所有原根
vector<int> Getall_primitive_root(int g, int n, int fhi_n) {
vector<int> res;
res.pb(g);
for (int i = 2; i < fhi_n; i++) {
if (__gcd(i, fhi_n) != 1) continue;
res.pb(pow_mod(g, i, n));
}
return res;
}
int main () {
getPrime(maxn, tot, ans);
int n;
while(~scanf("%d", &n)) {
if (n == 2) {
puts("1");
continue;
}
if (n == 4) {
puts("3");
continue;
}
if (!has_primitive_root(n)) {
puts("-1");
continue;
}
ll fhi_n = euler(n);
ll g = primitive_root(n, fhi_n);
vector<int> res = Getall_primitive_root(g, n, fhi_n);
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); i++) {
printf("%d%c", res[i], i == res.size() - 1 ? '\n' : ' ');
}
}
return 0;
}