Humble Numbers
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 comprise the set S. |
SAMPLE INPUT (file humble.in)
4 19
2 3 5 7
OUTPUT FORMAT
The Nth humble number from set S printed alone on a line.
SAMPLE OUTPUT (file humble.out)
27
Analysis
At the first glance of it, I missunderstood it as a DP problem. But later, I realized that we can simply make an array to store all of the "humble numbers", which is constructed in a way to add the minimum number among all the numbers just larger than the last one.
To archive it within little time, I use an array recording the power of the given prime number, for instance, the power of p[i] is called pri[i], and increasing the pri[i] to find the minimum number.
Code
/**//*
ID:braytay1
PROG:humble
LANG:C++
*/
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream fin("humble.in");
ofstream fout("humble.out");
int k,n;
int p[100],pri[100];
long long int humble[100001];
fin>>k>>n;
for (int i=0;i<k;i++) fin>>p[i];
memset(pri,0,sizeof(pri));
memset(humble,0,sizeof(humble));
humble[0]=1;
int max=-1;
for (int i=0;i<k;i++){
if (max<p[i]) max=p[i];
}
for (int i=1;i<=n;i++){
long long int min;
min=humble[i-1]*p[0]*p[0];
for (int k1=0;k1<k;k1++){
while(humble[pri[k1]]*p[k1]<=humble[i-1]) pri[k1]++;
if (humble[pri[k1]]*p[k1]<min) min=humble[pri[k1]]*p[k1];
}
humble[i]=min;
}
fout<<humble[n]<<endl;
return 0;
}