『算法-ACM 竞赛-数学-数论』原根(循环群生成元）

突然今天，我想不起什么是原根来了，查了一下定义，哎~这货不是离散数学，循环群生成元吗？？不是$<a_+>而是<a_*>是乘法而不是加法$
嘛玩意是原根：?

对于素数 p，如果存在一个正整数 1<a<p，使得 a1,a2,…,ap−1 模 p 的值取遍 1,2,…,p−1 的所有整数，称 a 是 p 的一个原根（primitive root），其实就是循环群的生成元。

$如果 aj≡ai(mod p)，则 i≡j(mod p−1)。这里有两个例子：$

5 是 7 的原根，因为 5–>3–>1–>6–>4–>2–>0，然后开始循环
2 不是 7 的原根，因为 2–>4–>1–>2–>4…，过早的循环了

说人话：好的

如果 g 是 P 的原根，就是$(g^P-1) ≡1 (mod P)$当且仅当指数为 P-1 的时候成立.(这里 P 是素数).
即 设 m 是正整数，a 是整数，若 a 模 m 的阶等于 φ(m)，则称 a 为模 m 的一个原根。
φ(m)：这货是欧拉函数

定理：

定理一：
设 p 是奇素数，则模 p 的原根存在； [3]
定理二：
设 g 是模 p 的原根，则 g 或者 g+p 是模的原根；
定理三：
设 p 是奇素数，则对任意，模的原根存在；
定理四：
设 1，则 g 是模的一个原根，则 g 与 g+中的奇数是模 2 的一个原根。

性质：

性质一：
对于任意正整数 a,m,如果(a,m) = 1,存在最小的正整数 d 满足 a^d≡1(mod m)，则有 d 整除 φ(m)，因此 Ordm(a)整除 φ(m)。这里的 d 被称为 a 模 m 的阶，记为 Ordm(a)。
　例如:求 3 模 7 的阶时，我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。
19 的原根有 2，2-4-8-16-13-7-14-9-。。。。
19 的原根就一定有 4， 4-16-7-9-。。。。。
有 8,16 所以也就是说如果一个数的原根没有 k 也就不存在 k 的幂。

性质二：
记 δ = Ordm(a)，则 a^1，……a^(δ-1)模 m 两两不同余。因此当 a 是模 m 的原根时，a^0^a^1，……a^(δ-1)构成模 m 的简化剩余系。
性质三：
模 m 有原根的充要条件是
$m= 1,2,4,p,2p,p^n,2p^n其中p是奇质数，n是任意正整数。$

性质四：
对正整数(a,m) = 1，如果 a 是模 m 的原根，那么 a 是整数模 n 乘法群（即加法群 Z/mZ 的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zn 的一个生成元。由于 Zn 有 φ(m)个元素，而它的生成元的个数就是它的可逆元个数，即 φ(φ(m))个，因此当模 m 有原根时，它有 φ(φ(m))个原根。
模 m 有原根的充要条件：

m=2 m=4 m=P^a m=2*P^a

怎么求？

我是笨逼枚举

1. 将 P-1 进行质因数分解
2. 枚举 i,并判断对于每个 i 是否都有(可以应用快速幂)
   第一个符合条件的 i 就是 P 的最小原根

$对于合数,只要将 2. 中的p-1替换成φ(p)即可.$

#include<cstdio>
#include<cmath>
inline int phi(int n)
{
    int zc=n,all=sqrt(n);
    for(int i=2;i<=all;i++)
	{
		if(n%i!=0)continue;
    	zc=zc/i*(i-1);
    	while(n%i==0)n/=i;
    }
    if(n>1)zc=zc/n*(n-1);
    return zc;
}
inline int pow(int x,const int y,const int mod)
{
	int res=1;
	for(int i=1;i<=y;i<<=1,x=x*x%mod)if(i&y)res=res*x%mod;
	return res;
}
inline int G(const int m)
{
	const int PHI=phi(m);
	for(int g=2;;g++)
	{
		bool fla=1;
		if(pow(g,PHI,m)!=1)continue;
		for(int i=1;i<PHI;i++)
			if(pow(g,i,m)==1)
			{
				fla=0;
				break;
			}
		if(fla)return g;
	}
}
int m,g;
int main()
{
	scanf("%d",&m);
    g=G(m);
    printf("%d",g);
    return 0;
}

在上面的代码中，容易发现，枚举的 i 并不是每个每个都有用的， 由性质 1 可得 枚举 i 只需要枚举 φ(m)的因数就好了

#include<cstdio>
#include<cmath>
inline int phi(int n)
{
    int zc=n,all=sqrt(n);
    for(int i=2;i<=all;i++)
	{
		if(n%i!=0)continue;
    	zc=zc/i*(i-1);
    	while(n%i==0)n/=i;
    }
    if(n>1)zc=zc/n*(n-1);
    return zc;
}
inline int pow(int x,const int y,const int mod)
{
	int res=1;
	for(int i=1;i<=y;i<<=1,x=(long long)x*x%mod)if(i&y)res=(long long)res*x%mod;
	return res;
}
int q[200001];
inline int G(const int m)
{
	const int PHI=phi(m);
	q[0]=0;
	for(int i=2;i<PHI;i++)if(PHI%i==0)q[++q[0]]=i;
	for(int g=2;;g++)
	{
		bool fla=1;
		if(pow(g,PHI,m)!=1)continue;
		for(int i=1;i<=q[0];i++)
			if(pow(g,q[i],m)==1)
			{
				fla=0;
				break;
			}
		if(fla)return g;
	}
}
int m,g;
int main()
{
	scanf("%d",&m);
    g=G(m);
    printf("%d",g);
    return 0;
}

最快的代码：

#include<cstdio>
#include<cmath>
inline int phi(int n)
{
    int zc=n,all=sqrt(n);
    for(int i=2;i<=all;i++)
	{
		if(n%i!=0)continue;
    	zc=zc/i*(i-1);
    	while(n%i==0)n/=i;
    }
    if(n>1)zc=zc/n*(n-1);
    return zc;
}
inline int pow(int x,const int y,const int mod)
{
	int res=1;
	for(int i=1;i<=y;i<<=1,x=(long long)x*x%mod)if(i&y)res=(long long)res*x%mod;
	return res;
}
int q[100001];
inline int G(const int m)
{
	const int PHI=phi(m);
	q[0]=0;
	const int limit=sqrt(PHI);int zc=PHI;
	for(int i=2;i<=limit;i++)
		if(zc%i==0)
		{
			q[++q[0]]=PHI/i;
			while(zc%i==0)zc/=i;
		}
	if(zc>1)zc=q[++q[0]]=PHI/zc;
	for(int g=2;;g++)
	{
		bool fla=1;
		if(pow(g,PHI,m)!=1)continue;
		for(int i=1;i<=q[0];i++)
			if(pow(g,q[i],m)==1)
			{
				fla=0;
				break;
			}
		if(fla)return g;
	}
}
int m,g;
int main()
{
	scanf("%d",&m);
    g=G(m);
    printf("%d",g);
    return 0;
}

代码怕写错，参考了一下。