USACO Section 3.1 Humble Numbers

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;
}


 

posted on 2008-08-20 23:11 幻浪天空领主 阅读(355) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿(1)

随笔档案(2)

文章分类(23)

文章档案(22)

搜索

最新评论

阅读排行榜

评论排行榜