Primitive Roots

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 949    Accepted Submission(s): 239


Problem Description We say that integer x, 0 < x < n, is a primitive root modulo n if and only if the minimum positive integer y which makes xy = 1 (mod n) true is φ(n) .Here φ(n) is an arithmetic function that counts the totatives of n, that is, the positive integers less than or equal to n that are relatively prime to n. Write a program which given any positive integer n( 2 <= n < 1000000) outputs all primitive roots of n in ascending order.  
Input Multi test cases.
Each line of the input contains a positive integer n. Input is terminated by the end-of-file seperator.  
Output For each n, outputs all primitive roots of n in ascending order in a single line, if there is no primitive root for n just print -1 in a single line.  
Sample Input 4 25  
Sample Output 3 2 3 8 12 13 17 22 23  
Source BestCoder Round #8
题意：求出 n的所有原根
分析： 利用原根的定义还是很好解决的，至于定义和定理可以看一下ACdream的博客  传送门
AC代码： #include #include #include #include using namespace std; vectorv; const int maxn=1e6+10; int zs[maxn]; //质数表 int ans[maxn]; bool vj(int n) //判断 是否满足 p^a||2*p^a &&p是奇质数 { if(n%2==0) n>>=1; if(!zs[n]) return 1; for(int i=3;i*i<=n;i+=2) { if(n%i==0) { while(n%i==0) n/=i; return n==1; } } return 0; } int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int quick_mod(int aa,int b,int mod) { long long c=1; long long a=aa; while(b) { if(b&1) { c*=a; c%=mod; } a*=a; a%=mod; b>>=1; } return (int) c; } int euler(int n) { int anss=n,t=n; for(int i=2;i*i<=n;i++) { if(t%i==0) { anss=anss/i*(i-1); while(t%i==0) t/=i; } } if(t!=1) anss=anss/t*(t-1); return anss; } void get_v(int n) { v.clear(); if(!zs[n]) return; for(int i=2;i*i<=n;i++) { if(n%i==0) { v.push_back(i); if(i*i!=n) v.push_back(n/i); } } } void solve(int n) { int p=euler(n); //printf("p=%d ",p); get_v(p); int flag=0; for(int i=2;i