Connection Status:
Competition Arena > Generators

Generators

SRM 243 · 2005-05-17 · by Olexiy

SRM 243 · 2005-05-17 · by Olexiy · Brute Force, Simple Math
Class Name: Generators
Return Type: int[]
Method Name: find
Arg Types: (int)
Problem Statement

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.

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 }

Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Generators with a public method vector<int> find(int p) · 38 test cases · 2 s / 256 MB per case

Submitting as anonymous