SPOJ Problem Set (classical)

3713. Primitive Root

Problem code: PROOT

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, r², r³, ... , r^p-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 ³¹ ) 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¹, 3², 3³ and 3⁴ are respectively 3, 4, 2 and 1 (mod 5). So, 3 is a primitive root of 5.

4¹, 4² , 4³ and 4⁴ are respectively 4, 1, 4 and 1 respectively. So, 4 is not a primitive root of 5.

Added by:	u.swarnaprakash
Date:	2009-01-14
Time limit:	3s
Source limit:	50000B
Languages:	All except: CLOJ ERL F# JS PERL 6 TECS
Resource:	Kurukshetra 09 OPC

hide comments


2010-04-21 14:35:03 Nic Roets A good computer scientist can solve this problem without number theory: 1. Know that ab%p = (a%p)(b%p)%p 2. Large exponents can be calculated efficiently because r^(2b+c)%p=(r^b%p)^2%p (r^c%p) % p. 3. Suppose r,r^2,..,r^(p-1) (mod p) are distinct. If r^a%p=0 then r^(a-1)%p=0 because r < p cannot have p as a factor and that leads to a contradiction. So r,r^2,.., r^(p-1) is a permutation of 1,2,..p-1. r^a%p=1 implies that a=p-1, otherwise r^(a+1)%p=r will imply a repetition in the list. So the first thing you program should check is that r^(p-1)%p=1. 4. f(a)=ra%p. Now all that remains is to check that the sequence 1,f(a),f(f(a)),... does not repeat more often than every p-1 entries. That can only occur at certain locations... Last edit: 2010-04-21 18:56:14*
2010-04-13 20:30:58 .::: Debanjan :::. Seems like some demented maths Olympiad question with sufficiently huge number of test cases.
2009-12-26 16:08:03 Nitin Gangahar Number theory :D