• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 幻浪天空領(lǐng)主 閱讀(371) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導(dǎo)航

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            四虎国产精品免费久久久| 久久本道伊人久久| 人人狠狠综合久久亚洲高清| 久久久久九九精品影院| 亚洲国产成人精品女人久久久| 国产精品中文久久久久久久| 三级三级久久三级久久| 久久精品国产亚洲av麻豆色欲 | 思思久久好好热精品国产| 97精品依人久久久大香线蕉97| 97精品伊人久久大香线蕉app| 久久久久亚洲AV无码专区桃色 | 国产精品成人99久久久久| 午夜精品久久影院蜜桃| 97久久超碰成人精品网站| 一级做a爰片久久毛片看看| 潮喷大喷水系列无码久久精品| 久久精品无码免费不卡| 久久国产热精品波多野结衣AV| 久久久久国产精品麻豆AR影院| 97久久精品人妻人人搡人人玩| 久久久久久久久久久久久久| 办公室久久精品| 久久久久成人精品无码中文字幕| 久久久免费观成人影院| 国产精品久久久久久影院| 久久久亚洲欧洲日产国码aⅴ| 日韩精品无码久久一区二区三| 久久综合九色综合精品| 久久久一本精品99久久精品66| 国产成人精品综合久久久久| 亚洲国产精品无码久久九九 | 国产精品一区二区久久精品无码| 亚洲精品乱码久久久久久蜜桃不卡 | 精品综合久久久久久888蜜芽| 中文字幕精品久久| 色婷婷久久综合中文久久一本| 一级做a爰片久久毛片16| 99国产欧美精品久久久蜜芽| 国产亚洲欧美成人久久片| 久久国产精品久久精品国产|