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 vector , containing all generators
of Zp that are less than p in ascending order.
DEFINITION
Class:Generators
Method:find
Parameters:int
Returns:vector
Method signature:vector find(int p)
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 }
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.