Skip to analysis
This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!
For a given set of K prime numbers S = {p1, p2, …, pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, and p1p2p3 (among others). This is the set of ‘humble numbers’ for the input set S. Note: The number 1 is explicitly declared not to be a humble number.
Your job is to find the Nth humble number for a given set S. Long integers (signed 32-bit) will be adequate for all solutions.
PROGRAM NAME: humble
INPUT FORMAT
Line 1: | Two space separated integers: K and N, 1 <= K <=100 and 1 <= N <= 100,000. |
Line 2: | K space separated positive integers that compose the set S. |
SAMPLE INPUT (file humble.in)
OUTPUT FORMAT
The Nth humble number from set S printed alone on a line.
SAMPLE OUTPUT (file humble.out)
CODE
Java
Loading…
C++
Loading…
Pascal
Loading…
ANALYSIS
Russ Cox
We compute the first n humble numbers in the “hum” array. For simplicity of implementation, we treat 1 as a humble number, and adjust accordingly.
Once we have the first k humble numbers and want to compute the k+1st, we do the following:
To speed up the search, we keep an index “pindex” of what h is for each prime, and start there rather than at the beginning of the list.
Back to top