RandomNumberGenerator | Topcoder Archive

Problem Statement

You want to create your own random number generator to create some random unique integers between 1 and a number radix-1, so that if you start working in another language that doesn't have one of these classes, you can port the one you've already written. A quick and easy way to make a random number generator is to take a Base number and raise it to a power called the seed. Then, divide this number by the radix and get the remainder, which you'll call the generator (in other words, generator = (Base^seed)%radix, where '^' denotes exponentiation). Your random number generator will return this generator as your first random number. Subsequent random numbers will be calculated like this: Multiply the previous random number by the generator. Divide this result by the radix, and return the remainder of this division as the next random number (in other words newRandom=(generator*oldRandom)%radix).

Obviously, not every seed will create a full set of random numbers: sometimes they repeat before generating every value between 1 and radix-1(inclusive). This is a bad seed. A good seed will generate every number between 1 and radix-1 (inclusive) before repeating. Your job is to create a function called howManyGoodSeeds that will return the number of good seeds between 1 and radix-1 (inclusive).

Definition

Class:: RandomNumberGenerator
Method:: howManyGoodSeeds
Parameters:: int, int
Returns:: int
Method signature:: int howManyGoodSeeds(int Base, int radix)
(be sure your method is public)

Notes

HINT: for finding numbers such as (999^1000)%1001: you won't want to calculate 999^1000 first, for that will overflow an integer. Instead use the following recurrence: (x^n)%m == ((x%m) * ((x^(n-1))%m))%m.

Constraints

radix will be an integer between 2 and 1000, inclusive.
Base will be between 1 and radix-1, inclusive.

Examples

```
1
```
```
10
```
```
Returns: 0
```
1 to any power is 1, and 1 will never generate other numbers other than one. Therefore 1 can not produce good seeds.
```
2
```
```
11
```
```
Returns: 4
```
1, 3, 7, 9 are all good seeds: seed=1 means generator = 2^1%11 = 2 and it generates them in this order: [2,4,8,5,10,9,7,3,6,1]. seed=3 means generator = 2^3%11 = 8 and it generates them in this order: [8,9,6,4,10,3,2,5,7,1]. seed=7 means generator = 2^7%11 = 7 and it generates them in this order: [7,5,2,3,10,4,6,9,8,1]. seed=9 means generator = 2^9%11 = 6 and it generates them in this order: [6,3,7,9,10,5,8,4,2,1]. Observe that 1 is at the end of every list. The number 10 always being the 5th element in each list is just an artifact of choosing 11 as a radix.
```
641
```
```
991
```
```
Returns: 0
```
```
3
```
```
257
```
```
Returns: 128
```
```
11
```
```
101
```
```
Returns: 40
```
```
1
```
```
2
```
```
Returns: 1
```

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)2024, Topcoder, Inc. All rights reserved.