PROOT  Primitive Root
In the field of Cryptography, prime numbers play an important role. We are interested in a scheme called "DiffieHellman" 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, r^{2}, r^{3}, ... , r^{p1} 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 3^{1}, 3^{2 }, 3^{3} and 3^{4} are respectively 3, 4, 2 and 1 (mod 5). So, 3 is a primitive root of 5.
4^{1}, 4^{2} , 4^{3} and 4^{4} are respectively 4, 1, 4 and 1 respectively. So, 4 is not a primitive root of 5.
hide comments
Aditya Kumar:
20150623 13:11:56
A helpful link : http://www.apfloat.org/prim.html 

Piyush Kumar:
20130623 16:40:15
interesting Maths :) 

Ouditchya Sinha:
20130519 04:13:37
Very nice problem, loved solving it. :) 

saket diwakar:
20130127 14:11:42
i love such problems.....:) 

Romal Thoppilan:
20110903 14:22:25
time limit should have been alleast 6s for nonmathematicians to solve it . 

Dark_night:
20110714 17:01:06
good prob...... 

The Champ:
20110621 17:46:36
loved solving this one ;) 

sandeep pandey:
20110204 16:38:14
Last edit: 20110331 20:33:59 

:(){ :: & };::
20100413 18:30:58


Nitin Gangahar:
20091226 15:08:03
Number theory :D 
Added by:  Swarnaprakash 
Date:  20090114 
Time limit:  0.727s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Kurukshetra 09 OPC 