首页 > 代码库 > 快速求原根的实现
快速求原根的实现
关于原根是什么以及这里的求法
http://www.cnblogs.com/linkzijun/p/6380486.html
在末尾可以看到我之前写的定义和求法以及求法的证明。。很巧妙。。
设要求原根的质数为P,这个算法的复杂度大概是O(P-1)*log(P-1),后面是P-1不同质因子的数量
(学习了下tls for的写法。。结果结尾忘了写分号。。崩了一次,囧
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=1e6+7; bool not_pr[maxn];int pr[maxn],sz,fac[maxn],fz,P; typedef long long ll; void Sieve(){ int i,j; for(i=2;i<maxn;++i){ if(!not_pr[i]) pr[sz++]=i; for(j=0;j<sz&&i*pr[j]<maxn;++j){ not_pr[i*pr[j]]=1; if(i%pr[j]==0) break; } } } void factor(int p){ fz=0;int tmp=p-1,i; for(i=0;i<sz;++i){ if(tmp==1) break; if(tmp%pr[i]==0){ for(tmp/=pr[i];tmp%pr[i]==0;tmp/=pr[i]); //这里是分号 fac[fz++]=pr[i]; } } if(tmp!=1) fac[fz++]=tmp; } ll mod_pow(ll a,ll b,ll p){ if(b==0) return 1; ll ans=1; while(b){ if(b&1) ans=(ans*a)%p; a=(a*a)%p; b>>=1; } return ans; } bool judge(int x){ int i; for(i=0;i<fz;++i){ if(mod_pow(x,(P-1)/fac[i],P)==1) return false; } return true; } int main(){ Sieve(); while(~scanf("%d",&P)){ factor(P); for(int i=2;;++i) if(judge(i)) {printf("%d\n",i);break;} } return 0; }
快速求原根的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。