求原根（模板）

2019-04-13 15:48发布

站内文章 / 模拟电子
13259 0 1184
数论令人头秃，原理就看看别人博客吧：数论之原根 #include #include #include #include #include #include #include #include #include #include #include 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  

热门文章