Humble Numbers
For a given set of K prime numbers S = {p1,p2, ..., pK}, consider the set of all numbers whose primefactors are a subset of S. This set contains, for example, p1, p1p2,p1p1,
and p1p2p3 (amongothers). This is the set of `humble numbers' for the input set S. Note: Thenumber 1 is explicitly declared not to be a humble number.
Your job is to find the Nth humble numberfor a given set S. Long integers (signed 32-bit) will be adequate for allsolutions.
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 printedalone on a line.
SAMPLE OUTPUT (file humble.out)
27
我只能说,这道题技巧性太强了…
我竟然SB地从1开始一个数一个数的判断是不是humble number。。。这不是找超时么。。。
看了官方的思路才做出来的
官方题解
我们在数组hum中计算出前n个丑数。为了实现起来更简单，我们把1也作为一个丑数，算法也要因此略微调整一下。
当我们已知前k个丑数，想得到第k+1个，我们可以这样做：
对于每个质数p 寻找最小的丑数h 使得h * p 比上一个丑数大
取我们找到的 h * p 中最小的一个：它就是下一个丑数 为了使搜索更快，我们可以为每个质数维护一个索引“pre[i]”表示每i个质数已经乘到了哪个丑数，每次都从那里开始，而不是再从头再来。
/*
ID:138_3531
LANG:C++
TASK:humble
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
using namespace std;
ifstream fin("humble.in");
ofstream fout("humble.out");
int n,k;
int a[101];
int h[100005];
int pre[101];
void input()
{
fin>>k>>n;
for (int i=0;i<k;i++)
{
fin>>a[i];
}
}
int main()
{
input();
h[0]=1;
for (int i=1;i<=n;i++)
{
int minn=0x7FFFFFFF;
for (int j=0;j<k;j++)
for (int p=pre[j];p<i;p++)
if (h[p]*a[j]>h[i-1])
{
if (h[p]*a[j]<minn)
minn=h[p]*a[j];
pre[j]=p;
break;
}
h[i]=minn;
}
fout<<h[n]<<endl;
return 0;
}