3520. 【NOIP2013模拟11.7B组】原根

2019-04-14 17:45发布

站内文章 / 模拟电子
14841 0 1313

Description

Input

有且只有一个正整数m。

Output

以递增序依次输出模m的所有原根，每行输出一个原根。

如果不存在模m的原根，输出-1。

Sample Input

7

Sample Output

3 5

Data Constraint

50%的数据，m≤ 200。

100%的数据，m ≤ 10000。

Hint

样例解释：
 

 Solution 

题目是简单的，完全按照题目描述的方式模拟就可以了。
主要是考察选手会不会对数学题头昏，以及gcd函数怎么写 意思就是暴力。时间复杂度O(m^2); 有人（某大佬）认为这样的时间复杂度过不了极限数据（其实我也是这么认为，但是不知为何偏偏就过了），于是想出了一种O(m*根号m*long m)的时间复杂度，这里来讲一下：首先我们知道如果1到fai(m)中可能有很多个d使得a^d=1(mod m)的，并且每两个相邻的d的间隔是一样的！也就是说d有“循环节”因为当a的d次方模完m后又会从1开始再乘a，当a再乘以d次方后又变回了1，即a^2d=1（mod m），如：2^3%7=1，2^6%7=1。总而言之，d是一直循环直到fai(m)为止的，就是说a^d=1(mod m)，a^2^d=1(mod m)，a^3^d=1(mod m)，......a^x^d=1(mod m)，a^f^a^i^(^m^)=1(mod m)那么我们又会得出一个结论：d一定是fai(d)的因数！所以我们可以先暴力求出fai函数，然后再根号fai(m)求出fai(m)的所有约数，再将每个约数用快速幂乘起来得出一个答案，再用这个答案mod m看看是否等于1，如果是，那么当前这个a就不是原根了。  

Code1

#include #include #include #include #include using namespace std; int n,p,x,s,ans=0; bool bz; int fai(int x){ int q=x; for(int i=2;i<=x;i++){ if(x%i==0){ q=q*(i-1)/i; while(x%i==0) x/=i; } } if(x>1) q=q*(x-1)/x; return q; } int gcd(int x,int y){ if(x%y==0) return y; else return gcd(y,x%y); } int main(){ freopen("math.in","r",stdin); freopen("math.out","w",stdout); scanf("%d",&n); if(n==1){printf("1");return 0;} p=fai(n); for(int i=1;i<=n-1;i++){ if(gcd(i,n)!=1) continue; x=s=i;bz=1; for(int j=1;j<=p-1;j++){ if(s==1){bz=0;break;} s=(s*x)%n; } if(bz){ans++;printf("%d ",i);} } if(!ans) printf("-1 "); return 0; }

Code2 

#include using namespace std; int zh[10010],ys[10010]; int m,phi=0,tot=0,cnt=0; bool bz[10010],check,all=0; int ksm(int x,int y) { int s=1; while (y) { if (y & 1) s=s*x%m; x=x*x%m; y>>=1; } return s; } int main() { freopen("math.in","r",stdin); freopen("math.out","w",stdout); scanf("%d",&m); if (m==0) return 0&puts("-1"); else if (m==1 || m==2) return 0&puts("1"); for (int i=2;i<=m;i++) if (!bz[i]) { zh[++tot]=i; if (m%i) continue; for (int j=1;j<=m/i;j++) bz[i*j]=true; } for (int i=1;i<=m;i++) if (!bz[i]) phi++; for (int i=1,x=phi;i<=tot && x>1;i++) if (x%zh[i]==0) { ys[++cnt]=zh[i]; while (x%zh[i]==0) x/=zh[i]; } for (int i=2;i  
作者：zsjzliziyang 
QQ:1634151125 
转载及修改请注明 
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/83216201  

热门文章