PQNumbers
SRM 137 · 2003-03-06 · by vorthys
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.
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.
2 2 0 Returns: 1
2 2 3 Returns: 8
2 3 7 Returns: 12
The example above.
3 5 5 Returns: 25
3 2 20 Returns: 108
Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PQNumbers with a public method int nthSmallest(int p, int q, int n) · 38 test cases · 2 s / 256 MB per case