模板-原根

2019-04-13 12:18发布

站内文章 / 模拟电子
16888 0 1489
1.原根定义：设m>1,gcd(a,m)=1,使得这里写图片描述成立的最小的r，称为a对模m的阶。 
2.定理：如果模m有原根，那么他一共有这里写图片描述个原根。这里的函数表示[1,m)中与m互质的个数
3.定理：如果p为素数，那么素数p一定存在原根，并且模p的原根的个数为这里写图片描述个。
 4.定理：假设m是正整数，a是整数，如果a模m的阶等于这里写图片描述，则称a为模m的一个原根。
5.模m有原根的充要条件：m=2,4,P^a,2*P^a……. 
求模素数P的原根的方法：对P-1素因子分解，即P-1=(P1^a1)(P2^a2)…..(Pk^ak)。，若恒有这里写图片描述成立，那么g就是P的原根(对于合数而言,只需要把p-1换成这里写图片描述即可) #include #include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const double pi= acos(-1.0); const double esp=1e-7; const int Maxn=1e6+10; int prime[Maxn];//存储素数 int sprime[Maxn];//存储P-1的素因子 bitsetpri;//结果只有0和1，判断是否为素数 int k;//记录Maxn以内的素数个数 int cnt;//记录素因子的个数 void is_prime() { pri.set();//将所有的二进制数都标为1 for(int i=2; i1) sprime[cnt++]=n;//可能只有自己一个素因子 } LL modexp(LL a,LL b,int mod)//快速幂取余 { LL res=1; while(b>0) { a=a%mod; if(b&1) res=res*a%mod; b=b>>1; a=a*a%mod; } return res; } int main() { int p; is_prime(); while(~scanf("%d",&p)) { Divide(p-1); for(int g=2; g

热门文章