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

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久婷婷五月综合色奶水99啪| 一级做a爰片久久毛片16| 久久国产精品成人片免费| 日日噜噜夜夜狠狠久久丁香五月| 久久久久亚洲AV片无码下载蜜桃| 波多野结衣中文字幕久久| 狠狠色伊人久久精品综合网| 久久久久久久精品成人热色戒| 97久久精品国产精品青草| 久久久久国产| 国产精品天天影视久久综合网| 久久精品国产亚洲7777| 久久久久久午夜成人影院 | 亚洲狠狠婷婷综合久久久久| 99久久婷婷免费国产综合精品| 欧美日韩精品久久久久| 国产三级久久久精品麻豆三级| 久久婷婷五月综合成人D啪| 国产亚洲综合久久系列| 伊人久久大香线蕉av一区| 久久播电影网| 99久久婷婷国产一区二区| 国产成人久久AV免费| 亚洲色欲久久久综合网| 亚洲色欲久久久久综合网| 久久久久18| 日韩久久久久中文字幕人妻| 国产91久久综合| 91麻精品国产91久久久久| 久久99国产亚洲高清观看首页| 三上悠亚久久精品| 久久99精品久久久久久久不卡| 亚洲精品乱码久久久久久| 亚洲中文久久精品无码| 久久天天躁夜夜躁狠狠躁2022 | 99re久久精品国产首页2020| 亚洲va国产va天堂va久久| 狠狠综合久久AV一区二区三区| 亚洲人成精品久久久久| 久久精品国产亚洲77777| 久久精品国产亚洲av高清漫画|