锐客网

  1. 首页 > it技术 > >

板子|求原根

数论板子

【板子|求原根】今天学了数论。。。求原根真的好暴力
设模数为p,
我们把 p ? 1 p-1 p?1分解质因数， p 1 , p 2 … p m p_1,p_2 \ldots p_m p1?,p2?…pm?对于每一个 2 ≤ i ≤ p ? 1 2 \leq i \leq p-1 2≤i≤p?1 ,判断 i p ? 1 p j % p i^{p-1 \over p_j} \%p ipj?p?1?%p是否为1，如果是，那么这个数就不是原根，否则就是
AC Code

#include #include #include using namespace std; int zys[50]; int p; int o; int n; int ksm(int a,int c,int b) { long long re=1; long long t=a; while(c) { if(c&1)re=re%b*t%b; t=t%b*t%b; c>>=1; } return re; } int pd(int x) { for(int i=1; i<=o; i++) { if(ksm(x,(p-1)/zys[i],p)%p==1)return 0; } return 1; } int main() { scanf("%d",&p); int pp=p; p--; for(int i=2; i<=sqrt(p); i++) { if(p==1)break; if(p%i==0) { o++; zys[o]=i; while(p%i==0) { p/=i; } } } if(p!=1) { o++; zys[o]=p; } p=pp; for(int i=2; i

    推荐阅读


    上一篇：退役了

    下一篇：mysql5.6.15忘记数据库的root密码（）