PQNumbers | Topcoder Archive

Problem Statement

For any integers p and q, both greater than one, define the [p,q]-numbers to be all integers of the form (p^i * q^j), for non-negative integers i and j. Your task is to calculate the nth-smallest [p,q]-number, where nth-smallest means that there are exactly n smaller [p,q]-numbers.

For example, the sequence of [2,3]-numbers is 1,2,3,4,6,8,9,12,..., so 12 is the nth-smallest [2,3]-number for n=7.

Create a class PQNumbers containing a method nthSmallest that takes three integers, p, q, and n, and returns the nth-smallest [p,q]-number.

Definition

Class:: PQNumbers
Method:: nthSmallest
Parameters:: int, int, int
Returns:: int
Method signature:: int nthSmallest(int p, int q, int n)
(be sure your method is public)

Notes

p^i means p to the i-th power, not xor.

Constraints

p and q are both between 2 and 20, inclusive.
n is between 0 and 20, inclusive.
The nth-smallest [p,q]-number is no greater than 1 million.

Examples

```
2
```
```
3
```
```
7
```
```
Returns: 12
```
The example above.
```
7
```
```
5
```
```
15
```
```
Returns: 3125
```
```
10
```
```
4
```
```
15
```
```
Returns: 4000
```
```
9
```
```
6
```
```
17
```
```
Returns: 17496
```
```
2
```
```
8
```
```
10
```
```
Returns: 1024
```
```
7
```
```
13
```
```
0
```
```
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.