定义
对于某一个$g\in [0,p)$，如果对于$\{0,1,\cdots p-1\}$中每一个与$p$互质的数$x$，都存在一个$k$使得$g^k \equiv x \mod p$，那么就称$g$是$p$的一个原根。也就是说，$g^0,g^1,\cdots g^{\varphi (n) - 1}$在模$n$的意义下两两不同。
检测一个数是否为$p$的原根
现在还没有快速的计算一个数的原根的算法。但是，我们有一种比较快的检测一个数是否为$p$的原根的方法。
阶 multiplicative order
在模$p$的意义下，定义某个满足$gcd(a,p) = 1$的$a$的阶为，满足$a^k \equiv 1\mod p$的最小正整数$k$，记为$\delta_p(a)$。
阶有一些性质：
1）如果$a^N \equiv 1 \mod p$，那么$N$一定是$a$的阶的倍数。并且，根据欧拉定理，$N$一定是$\varphi(p)$的因数。
2）原根的阶等于$\varphi(p)$。
容易推出，对于一个$x$，如果它不是$p$的原根，那么他的阶一定小于$\varphi(p)$并且是$\varphi(p)$的因数。我们只需要对于$\varphi(p)$的每一个因数$d$，判断$x^d \equiv 1\mod p$是否成立就好了。实际上，由于阶的性质，我们处理出$\varphi(p)$的所有质因子$pr_1,pr_2\cdots pr_k$，然后判断$x^{\varphi (p)\over pr_i}\equiv 1\mod p$是否成立，就可以判断$x$是不是原根。因为如果$x$的阶小于$\varphi(p)$，那么${\varphi(p)\over pr_i}$中，至少有一个是$\delta_p (x) $的倍数。
这个检测的复杂度应该是$O(\sqrt p \log p)$的。
求最小原根
求最小原根的算法：从2开始依次枚举，依次检验每一个枚举到的数，当检验出一个数为原根的时候就退出。这个算法的复杂度是与最小原根的大小相关的。呃，一个数最小原根的大小大概也许一般是比较小的。
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
| #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
template <class T>
inline void read(T &x)
{
x=0; char c=getchar(); int f=1;
while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=32010;
int pri[N],num,flg[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void predo(int n){for(int i=2;i<=n;++i){if(!flg[i])pri[num++]=i; for(int j=0;j<num&&pri[j]*i<=n;++j){flg[i*pri[j]]=1; if(i%pri[j]==0) break;}}}
int d[N],tot,mod;
int Pow(int x,int y){int res=1;while(y){if(y&1) res=res*(ll)x%mod; x=x*(ll)x%mod,y>>=1;}return res;}
void get(int p){tot=0; for(int j=0;j<num&&pri[j]*pri[j]<=p;++j){if(p%pri[j]==0){d[++tot]=pri[j]; while(p%pri[j]==0) p/=pri[j]; }} if(p>1) d[++tot]=p; }
bool che(int x){if(gcd(x,mod)!=1) return 0;for(int i=1;i<=tot;++i) if(Pow(x,(mod-1)/d[i])==1) return 0; return 1;}
int main()
{
predo(N-10); read(mod),get(mod-1);
for(int i=2;i<mod;++i)
if(che(i)){printf("%d",i); break;}
return 0;
}
|
原根数量&&求一个数所有的原根
对于一个$p$，如果它的原根存在，那么它的原根的数量是$\varphi(\varphi(p))$。
假设$g$是$p$的原根，并且$gcd(i,\varphi(p))=1$，那么$g^i$也是$p$的一个原根。原因是当$gcd(i,\varphi(p))=1$，$i$的$k$倍可以遍历$\varphi(p)$的剩余集，也就是说，$g^i$的幂次可以取遍$[0,p)$中，所有与$p$互质的数。
因此，对于一个数$p$，如果它的原根存在，那么一定有$\varphi(\varphi(p))$个。
由此，我们可以得到求一个数所有的原根的算法：先求出最小原根，然后取所有与$\varphi(p)$互质的$i$，就可以得到所有的原根了。
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
| #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define PB push_back
#define ll long long
using namespace std;
template <class T>
inline void read(T &x)
{
x=0; char c=getchar(); int f=1;
while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=1000010;
int pri[N],num,flg[N],phi[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void predo(int n)
{
for(int i=2;i<=n;++i)
{
if(!flg[i])pri[num++]=i,phi[i]=i-1;
for(int j=0;j<num&&pri[j]*i<=n;++j)
{
flg[i*pri[j]]=1;
if(i%pri[j]==0) {phi[i*pri[j]]=phi[i]*pri[j]; break;}
else phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
}
int d[N],tot,mod;
int Pow(int x,int y){int res=1;while(y){if(y&1) res=res*(ll)x%mod; x=x*(ll)x%mod,y>>=1;}return res;}
void get(int p){tot=0; for(int j=0;j<num&&pri[j]*pri[j]<=p;++j){if(p%pri[j]==0){d[++tot]=pri[j]; while(p%pri[j]==0) p/=pri[j]; }} if(p>1) d[++tot]=p; }
bool che(int x){if(gcd(x,mod)!=1) return 0;for(int i=1;i<=tot;++i) if(Pow(x,phi[mod]/d[i])==1) return 0; return 1;}
int Get(){get(phi[mod]);for(int i=2;i<mod;++i) if(che(i)) return i;}
bool check(int p)
{
if(p==2||p==4) return 1; if(p%2==0) p/=2; if(p%2==0) return 0;
for(int j=1;pri[j]*pri[j]<=p&&j<num;++j) if(p%pri[j]==0){while(p%pri[j]==0) p/=pri[j]; return p==1;}
return 1;
}
vector<int> ans;
void solve()
{
if(!check(mod)){ puts("-1"); return;}
if(mod==2) {puts("1"); return;}
int g=Get(),k=g; ans.clear();
for(int i=1;i<phi[mod];++i){if(gcd(i,phi[mod])==1) ans.PB(k); k=k*(ll)g%mod;}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();++i) printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
}
int main()
{
predo(N-10);
while(~scanf("%d",&mod)) solve();
return 0;
}
|
原根存在的条件
丢一个结论在这里：一个数$m$存在原根，当且仅当$m=2,4,p^a,2\times p^a$，其中$p$为奇质数，$a$为正整数。
所以把判断一个数是否有原根的函数放在这里。代码中，pri数组下标从0开始，$pri[0]=2,pri[1]=3$。
1
2
3
4
5
6
| bool check(int p)
{
if(p==2||p==4) return 1; if(p%2==0) p/=2; if(p%2==0) return 0;
for(int j=1;pri[j]*pri[j]<=p&&j<num;++j) if(p%pri[j]==0){while(p%pri[j]==0) p/=pri[j]; return p==1;}
return 1;
}
|