51 nod 1135原根

2019-04-14 20:23发布

站内文章 / 模拟电子
10112 0 1521

51 nod  1135原根




题意： a 模 m 的阶定义： gcd(a,m)=1,使得这里写图片描述成立的最小的 r，称为 a 对 模m 的 阶   那么整个题就是要求  a^(p-1) % p==1 成立的 最小  a ;
方法：  copy   by  点击打开链接 分解质因子， 对任何整数 a ∈[1,p-1]， 检验 a 是否为 p 的原根， 检验方法：a^((p-1)/p1),a^((p-1)/p2),...a^((p-1)/pm) 中是否存在一个 模p 等于 1 ， 存在的话 a 就不是 模p 的一个原根（即p-1就不是a对模p的阶），否则a就为原根。
#include using namespace std; int pri[50010]; bool vis[50010]; int A[50010]; int len1,len2; typedef long long ll; void init() { memset(vis,false,sizeof vis); len1=0; for(int i=2;i<50010;i++) { if(!vis[i]) pri[len1++]=i; for(int j=0;j>=1; } if(ans==1) return 1; return 0; } void Div(int m) { len2=0; for(int i=0;i1) A[len2++]=m; } int main() { int p; init(); while(scanf("%d",&p)!=EOF) { Div(p-1); int fla; for(int a=2;a

热门文章