917. The nth Number Built From These Primes
Given k distinct primes, consider every positive integer whose prime factors
all come from that set. 1 qualifies, because it has no prime factors at all.
List those integers in increasing order and print the nth, counting from 1.
``` primes 2 7 13, n = 12 -> 49 1 2 4 7 8 13 14 16 26 28 32 49
primes 2, n = 1 -> 1 primes 5, n = 10 -> 1953125 which is 5^9 ```
## What most people try first
Testing every integer upwards and factorising it is hopeless: the answers
thin out fast, and with primes 11 and 13 the fortieth such number is
already 353829047.
Generating all products p1^a * p2^b * ... up to a limit and sorting needs the
limit guessed in advance, and the count of candidates is not known until after
the guess.
## The method, and the derived key
Every qualifying number after 1 is p * v for some prime p in the set and
some SMALLER qualifying number v. So build the list in order, and keep, for
each prime, a pointer into the list already built:
vals = [1]
idx[i] = 0 for every prime
while len(vals) < n:
cand = min over i of prime[i] * vals[idx[i]]
for every i with prime[i] * vals[idx[i]] == cand:
idx[i] = idx[i] + 1
append cand to vals
print vals[n-1]
The candidate for prime i is the DERIVED key: not the prime, and not the
value, but their product. Advancing every pointer that produced the winning
candidate, rather than just one, is how duplicates are avoided: 6 is both
2 * 3 and 3 * 2, and without the loop it would be listed twice.
## The heap version, and when to prefer it
With k large, scanning all k candidates per step is O(nk). A min-heap of
the k candidates keyed by the product makes each step O(log k):
push (prime[i], prime[i], 0) for every i
repeat n - 1 times:
pop the smallest product; if it equals the last value appended, pop again
append it and push (prime * vals[idx+1], prime, idx+1)
At k = 100 and n = 10^5 the scan is 10^7 operations and the heap is about
10^5 * 7. Both finish; the scan is simpler and the heap is what generalises.
Knowing that the pointer version exists is the point, because it is the one
that avoids the duplicate problem for free.
## Why it is correct
By induction, vals holds the qualifying numbers in increasing order.
Suppose that holds for the first m entries. The next qualifying number x is
larger than vals[m-1] and factors as p * v with v qualifying and
v < x, so v is already in vals. For that prime p, the pointer sits at the
smallest index whose product with p exceeds vals[m-1], because the pointer
advanced exactly when its product was appended. So p * vals[idx[p]] <= x. And
no candidate is smaller than x, since every candidate is a qualifying number
above vals[m-1]. So the minimum candidate is exactly x.
## The boundary that breaks a careless implementation
Advance EVERY pointer whose candidate equals the winner, not just the first
one found. With primes 2 and 3 the value 6 appears as both candidates at
the same moment, and advancing one pointer makes the next step produce 6
again, so the list gains a duplicate and every later answer is shifted.
1 is the first qualifying number, so n = 1 prints 1 whatever the primes
are. Starting the list at the smallest prime is the other common off-by-one.
## Overflow
The answer is guaranteed at most 2 * 10^9, and 2000000000 is smaller than the
signed 32-bit maximum of 2147483647, so the ANSWER fits in 32 bits. The CANDIDATES do not. A candidate is prime * value with the prime up
to 1000, so candidates reach 2 * 10^12 and must be computed in 64 bits. A
32-bit multiply wraps them to arbitrary values, including negative ones, which
then win the minimum and corrupt the list from that point on.
## Related problems
Problem #784 finds the nth number divisible by either of two values and
#785 the kth divisible by none of several primes. Both are counted with
inclusion and exclusion and found by binary search, because "how many
qualifying numbers are at most x" has a closed form there. Here it does not,
because the qualifying set is closed under multiplication rather than defined
by divisibility, so the numbers have to be generated.
## Cost
Time O(nk) for the pointer version, O(n log k) with a heap. Space O(n + k).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ 100` - `2 ≤ prime ≤ 1000`, all distinct - The answer is at most `2000000000`.
Input
The first line contains two integers n and k.
The second line contains k distinct primes.
Output
Print one integer on its own line: the nth smallest positive integer whose prime factors all come from the given set, counting 1 as the first. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.