TopCoder problem "Generators" used in SRM 243 (Division I Level One , Division II Level Two)



Problem Statement

    Let p be a prime number. Zp is a set of numbers from 1 to (p - 1), inclusive. An element a of Zp is a generator of Zp if the set {1, a%p, (a*a)%p, (a*a*a)%p, ..., (a^(p-2))%p} is equal to Zp (here '%' represents the modulus operator).

You will be given a prime p. Write a method that returns a int[], containing all generators of Zp that are less than p in ascending order.
 

Definition

    
Class:Generators
Method:find
Parameters:int
Returns:int[]
Method signature:int[] find(int p)
(be sure your method is public)
    
 

Notes

-For all a and b, (a * b) % p is equal to ((a % p) * (b % p)) % p.
 

Constraints

-p is a prime between 3 and 1000, inclusive.
 

Examples

0)
    
3
Returns: {2 }
For p = 3 set {1, a % 3} must be equal to {1, 2} - so the only generator is 2.
1)
    
5
Returns: {2, 3 }
Let's check all numbers between 2 and (p - 1), inclusive, for being a generator.

a = 2. a2 % 5 = 4. a3 % 5 = 8 % 5 = 3. The set {1, a, a2, a3} is equal to {1, 2, 4, 3} and contains all non-zero numbers from Z5. Thus 2 is a generator.

a = 3. a2 % 5 = 4. a3 % 5 = 2. The set {1, a, a2, a3} is equal to {1, 3, 4, 2} and contains all non-zero numbers from Z5. Thus 3 is a generator.

a = 4. a2 % 5 = 1. a3 % 5 = 4. The set {1, a, a2, a3} is equal to {1, 4, 1, 4} and does NOT contain all non-zero numbers from Z5. Thus 4 is NOT a generator.
2)
    
13
Returns: {2, 6, 7, 11 }
3)
    
19
Returns: {2, 3, 10, 13, 14, 15 }
4)
    
337
Returns: 
{10, 15, 19, 20, 22, 23, 29, 31, 33, 34, 44, 45, 46, 51, 53, 60, 61, 67, 68, 70, 71, 73, 80, 83, 87, 89, 90, 93, 99, 101, 106, 109, 114, 116, 118, 120, 124, 130, 132, 134, 139, 143, 151, 152, 154, 160, 161, 166, 171, 176, 177, 183, 185, 186, 194, 198, 203, 205, 207, 213, 217, 219, 221, 223, 228, 231, 236, 238, 244, 247, 248, 250, 254, 257, 264, 266, 267, 269, 270, 276, 277, 284, 286, 291, 292, 293, 303, 304, 306, 308, 314, 315, 317, 318, 322, 327 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3043

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7218&pm=3043

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Brute Force, Simple Math