题意：给定模P，n个c,判断c是否是p的原根， 《数论概论》中“幂模p与原根”一章中有提到阶的概念： 如果gcd(c,p)=1，则a模p的阶是指使得 a^d=1（mod p）的最小指数d(d>=1)； 例如2、3、4、5、6模7的阶分别是3、6、3、6、2。 重要性质：一个数a模p的阶e总能整除p-1。  所以可以枚举p-1的所有因子factor  （不包括p-1），如果存 在小于p-1的因子满足a^factor=1(mod p) 则说明a模p的阶不是p-1； #include #include #include #include #include #include #include #include #include using namespace std; int a[10000]; int mod,cnt; void pr(int p) { a[0]=1;cnt=0; for(int i=2;i<=(int)sqrt(p);i++) { if(p%i==0) { a[++cnt]=i; a[++cnt]=p/i; } } } ll powmod(ll x,ll n) { if(n==0) return 1%mod; ll temp=powmod(x,n>>1); temp=temp*temp%mod; if(n&1) temp=temp*x%mod; return temp; } int main() { int n; while(scanf("%d%d",&mod,&n)&&mod||n) { int c; for(int i=1;i<=n;i++) { bool tag=false; memset(a,0,sizeof(a)); scanf("%d",&c); pr(mod-1); for(int j=0;j<=cnt;j++) { if(powmod(c,a[j])==1) { tag=true; break; } } if(powmod(c,mod-1)!=1) tag=false; if(tag) printf("NO "); else printf("YES "); } } return 0; }
In the field of Cryptography, prime numbers play an important role. We are interested in a scheme called "Diffie-Hellman" key exchange which allows two communicating parties to exchange a secret key. This method requires a prime number p and r which is a primitive root of p to be publicly known. For a prime number p, r is a primitive root if and only if it's exponents r, r2, r3, ... , rp-1 are distinct (mod p). Cryptography Experts Group (CEG) is trying to develop such a system. They want to have a list of prime numbers and their primitive roots. You are going to write a program to help them. Given a prime number p and another integer r < p , you need to tell whether r is a primitive root of p.

Input

There will be multiple test cases. Each test case starts with two integers p ( p < 2 31 ) and n (1 ≤ n ≤ 100 ) separated by a space on a single line. p is the prime number we want to use and n is the number of candidates we need to check. Then n lines follow each containing a single integer to check. An empty line follows each test case and the end of test cases is indicated by p=0 and n=0 and it should not be processed. The number of test cases is atmost 60.

Output

For each test case print "YES" (quotes for clarity) if r is a primitive root of p and "NO" (again quotes for clarity) otherwise.

Example

Input: 5 2 3 4 7 2 3 4 0 0 Output: YES NO YES NO

Explanation

In the first test case 31, 32 , 33 and 34 are respectively 3, 4, 2 and 1 (mod 5). So, 3 is a primitive root of 5. 41, 42 , 43 and 44 are respectively 4, 1, 4 and 1 respectively. So, 4 is not a primitive root of 5.