896. Numbers Built Only From These Primes

A set of m distinct primes is given. A positive integer is BUILDABLE when every prime factor it has comes from that set. The number 1 is buildable, having no prime factors at all.

Print the nth buildable number in increasing order, counting from 1.

primes 2 3 5, n = 10 -> 12 primes 2 7, n = 12 -> 64 primes 11 13 17, n = 1 -> 1 primes 2, n = 20 -> 524288

For 2 3 5 the sequence starts 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, so the 10th is 12. For 2 alone it is the powers of two, and the 20th is 2^19 = 524288.

## What most people try first

Testing each integer in turn. The 100000th buildable number for 2 3 5 7 11 is 280, but for 2 3 alone the 1000th is about 3.6 * 10^16, so almost every candidate fails and the test itself costs a factorisation. This is hopeless.

Generating everything below a bound with nested loops. The bound is not known in advance and the loop nesting depends on m, which is an input.

## Build the sequence forwards

Every buildable number other than 1 is some earlier buildable number multiplied by one of the primes. So keep the sequence built so far, and for each prime a POSITION into it, saying which earlier value that prime should multiply next.

vals = [1] idx[i] = 0 for every prime i h = min-heap of (vals[idx[i]] * p[i], i), seeded for every i while vals has fewer than n entries: (v, i) = pop h if v is not equal to the last value in vals: append v idx[i] = idx[i] + 1 push (vals[idx[i]] * p[i], i) into h answer = vals[n-1]

## What #1329 does, and why the bounds here change the method

Problem 1329 is this question with the primes fixed at 2, 3 and 5 and n capped at 1500. With exactly three multipliers it takes the smallest of three candidates by writing out a three-way comparison, which is simple and perfect at that size.

Here m reaches 100 and n reaches 100000. Taking the smallest of m candidates by scanning them is O(nm), which is 10^7, and while that is survivable it is the wrong shape: the candidates change by exactly ONE entry per step, so rescanning all of them throws away everything known from the previous step. A heap of the m candidates updates in O(log m) and the whole run is O(n log m), about 7 * 10^5.

That is the general lesson. When a minimum is taken repeatedly over a set that changes by one element at a time, a linear scan is doing m work to absorb one change.

## The duplicate that must not slip through

6 is 2 * 3 and also 3 * 2, so two different primes produce it. If both copies are appended, the sequence gains a phantom entry and every later answer is shifted down by one.

The fix is the line if v is not equal to the last value in vals. The pops come out in non-decreasing order, so equal values are always adjacent, and comparing with the last appended value catches every repeat. Note that the pointer for the prime that produced the duplicate still advances; skipping the advance would loop forever on the same value.

## Overflow, with the actual magnitude

The answer is guaranteed to be at most 10^18, which needs 64 bits, since a signed 32-bit integer stops at 2147483647 and even the twentieth power of two is already past a 16-bit type. The 60th power of two is 576460752303423488, which is a declared test.

The candidates are the danger. A value near 10^18 multiplied by a prime up to 1000 would be 10^21, which overflows a signed 64-bit integer, whose ceiling is about 9.2 * 10^18. Guard it by DIVIDING rather than multiplying:

if vals[idx[i]] <= 1000000000000000000 / p[i]: push the product else: this prime is finished

A prime whose candidates have all passed 10^18 can never contribute again, because its candidates only grow, so dropping it is safe.

## Why the pointer never runs past the end

When (v, i) is popped, v = vals[idx[i]] * p[i] and p[i] >= 2, so v > vals[idx[i]]. Since v was the minimum of the heap, it is at most the value just appended, so vals[idx[i]] is strictly less than the last entry of vals. That means idx[i] is not the last position, so idx[i] + 1 is a valid index. The advance is always legal, with no bounds check needed.

## Related problems

Problem 1329 is the fixed three-prime version. Problem 887 is the same k-way-merge machinery over lists that already exist, whereas here the lists are being generated as they are consumed, which is why the pointers index into the OUTPUT.

## Cost

Time O(n log m). Space O(n + m).

Constraints - `1 ≤ m ≤ 100` - `1 ≤ n ≤ 100000` - `2 ≤ p[i] ≤ 1000`, all distinct primes - It is guaranteed that the answer is at most 10^18.