天梯赛选拔补题---1235帮的Kth(多路归并， 打表)

题意如下：

整数1,2,3,5成立了一个帮会：只限能够1，2，3，5内部相乘得到的自然数入会（即可以写成2的某次方，3的某次方与5的某次方的积的形式。如60=4x15=2​2​​x3x5，故60是1234帮的）。按从小到大的顺序，前十个会员是：1,2,3,4,5,6,8,9,10,12。请编写程序，输出排在第K个位置的整数（第一个是1，第六个6，第十个是12）。 因为K可能取到较大的值，请尽量使用高效算法。

输入格式:

输入一个位排位号（ 1 − − N 1--N 1−−N）

输出格式:

直接输出排在第 K K K个的会员。

输入样例:

12 12 12

输出样例:

16 16 16

算法1(打表)

设1235帮的成员最大值不超过int范围，很明显满足条件的数不超过8000个， 因为假设一个数 n n n是1235帮的,那么 n n n一定可以表示为 n = 2 a 3 b 5 c n = 2^a3^b5^c n=2a3b5c,其中 a < = l o g 2 N ， b < = l o g 3 N , c < = l o g 5 N a<=log_2N，b <= log_3N, c <= log_5N a<=log2​N，b<=log3​N,c<=log5​N,其中 N N N是int最大值2147483647，由乘法原理有n的个数为 l o g 2 N ∗ l o g 3 N ∗ l o g 5 N < 8000 log_2N*log_3N*log_5N < 8000 log2​N∗log3​N∗log5​N<8000,因此int范围内的数是可以存在数组里的，不会爆内存， 用暴力算法把所有 1 − 2147483647 1-2147483647 1−2147483647的所有值算出来即可。
代码如下：

#include
using namespace std;
int f[] = {0,1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100,108,120,125,128,135,144,150,160,162,180,192,200,216,225,240,243,250,256,270,288,300,320,324,360,375,384,400,405,432,450,480,486,500,512,540,576,600,625,640,648,675,720,729,750,768,800,810,864,900,960,972,1000,1024,1080,1125,1152,1200,1215,1250,1280,1296,1350,1440,1458,1500,1536,1600,1620,1728,1800,1875,1920,1944,2000,2025,2048,2160,2187,2250,2304,2400,2430,2500,2560,2592,2700,2880,2916,3000,3072,3125,3200,3240,3375,3456,3600,3645,3750,3840,3888,4000,4050,4096,4320,4374,4500,4608,4800,4860,5000,5120,5184,5400,5625,5760,5832,6000,6075,6144,6250,6400,6480,6561,6750,6912,7200,7290,7500,7680,7776,8000,8100,8192,8640,8748,9000,9216,9375,9600,9720,10000,10125,10240,10368,10800,10935,11250,11520,11664,12000,12150,12288,12500,12800,12960,13122,13500,13824,14400,14580,15000,15360,15552,15625,16000,16200,16384,16875,17280,17496,18000,18225,18432,18750,19200,19440,19683,20000,20250,20480,20736,21600,21870,22500,23040,23328,24000,24300,24576,25000,25600,25920,26244,27000,27648,28125,28800,29160,30000,30375,30720,31104,31250,32000,32400,32768,32805,33750,34560,34992,36000,36450,36864,37500,38400,38880,39366,40000,40500,40960,41472,43200,43740,45000,46080,46656,46875,48000,48600,49152,50000,50625,51200,51840,52488,54000,54675,55296,56250,57600,58320,59049,60000,60750,61440,62208,62500,64000,64800,65536,65610,67500,69120,69984,72000,72900,73728,75000,76800,77760,78125,78732,80000,81000,81920,82944,84375,86400,87480,90000,91125,92160,93312,93750,96000,97200,98304,98415,100000,101250,102400,103680,104976,108000,109350,110592,112500,115200,116640,118098,120000,121500,122880,124416,125000,128000,129600,131072,131220,135000,138240,139968,140625,144000,145800,147456,150000,151875,153600,155520,156250,157464,160000,162000,163840,164025,165888,168750,172800,174960,177147,180000,182250,184320,186624,187500,192000,194400,196608,196830,200000,202500,204800,207360,209952,216000,218700,221184,225000,230400,233280,234375,236196,240000,243000,245760,248832,250000,253125,256000,259200,262144,262440,270000,273375,276480,279936,281250,288000,291600,294912,295245,300000,303750,307200,311040,312500,314928,320000,324000,327680,328050,331776,337500,345600,349920,354294,360000,364500,368640,373248,375000,384000,388800,390625,393216,393660,400000,405000,409600,414720,419904,421875,432000,437400,442368,450000,455625,460800,466560,468750,472392,480000,486000,491520,492075,497664,500000,506250,512000,518400,524288,524880,531441,540000,546750,552960,559872,562500,576000,583200,589824,590490,600000,607500,614400,622080,625000,629856,640000,648000,655360,656100,663552,675000,691200,699840,703125,708588,720000,729000,737280,746496,750000,759375,768000,777600,781250,786432,787320,800000,810000,819200,820125,829440,839808,843750,864000,874800,884736,885735,900000,911250,921600,933120,937500,944784,960000,972000,983040,984150,995328,1000000,1012500,1024000,1036800,1048576,1049760,1062882,1080000,1093500,1105920,1119744,1125000,1152000,1166400,1171875,1179648,1180980,1200000,1215000,1228800,1244160,1250000,1259712,1265625,1280000,1296000,1310720,1312200,1327104,1350000,1366875,1382400,1399680,1406250,1417176,1440000,1458000,1474560,1476225,1492992,1500000,1518750,1536000,1555200,1562500,1572864,1574640,1594323,1600000,1620000,1638400,1640250,1658880,1679616,1687500,1728000,1749600,1769472,1771470,1800000,1822500,1843200,1866240,1875000,1889568,1920000,1944000,1953125,1966080,1968300,1990656,2000000,2025000,2048000,2073600,2097152,2099520,2109375,2125764,2160000,2187000,2211840,2239488,2250000,2278125,2304000,2332800,2343750,2359296,2361960,2400000,2430000,2457600,2460375,2488320,2500000,2519424,2531250,2560000,2592000,2621440,2624400,2654208,2657205,2700000,2733750,2764800,2799360,2812500,2834352,2880000,2916000,2949120,2952450,2985984,3000000,3037500,3072000,3110400,3125000,3145728,3149280,3188646,3200000,3240000,3276800,3280500,3317760,3359232,3375000,3456000,3499200,3515625,3538944,3542940,3600000,3645000,3686400,3732480,3750000,3779136,3796875,3840000,3888000,3906250,3932160,3936600,3981312,4000000,4050000,4096000,4100625,4147200,4194304,4199040,4218750,4251528,4320000,4374000,4423680,4428675,4478976,4500000,4556250,4608000,4665600,4687500,4718592,4723920,4782969,4800000,4860000,4915200,4920750,4976640,5000000,5038848,5062500,5120000,5184000,5242880,5248800,5308416,5314410,5400000,5467500,5529600,5598720,5625000,5668704,5760000,5832000,5859375,5898240,5904900,5971968,6000000,6075000,6144000,6220800,6250000,6291456,6298560,6328125,6377292,6400000,6480000,6553600,6561000,6635520,6718464,6750000,6834375,6912000,6998400,7031250,7077888,7085880,7200000,7290000,7372800,7381125,7464960,7500000,7558272,7593750,7680000,7776000,7812500,7864320,7873200,7962624,7971615,8000000,8100000,8192000,8201250,8294400,8388608,8398080,8437500,8503056,8640000,8748000,8847360,8857350,8957952,9000000,9112500,9216000,9331200,9375000,9437184,9447840,9565938,9600000,9720000,9765625,9830400,9841500,9953280,10000000,10077696,10125000,10240000,10368000,10485760,10497600,10546875,10616832,10628820,10800000,10935000,11059200,11197440,11250000,11337408,11390625,11520000,11664000,11718750,11796480,11809800,11943936,12000000,12150000,12288000,12301875,12441600,12500000,12582912,12597120,12656250,12754584,12800000,12960000,13107200,13122000,13271040,13286025,13436928,13500000,13668750,13824000,13996800,14062500,14155776,14171760,14348907,14400000,14580000,14745600,14762250,14929920,15000000,15116544,15187500,15360000,15552000,15625000,15728640,15746400,15925248,15943230,16000000,16200000,16384000,16402500,16588800,16777216,16796160,16875000,17006112,17280000,17496000,17578125,17694720,17714700,17915904,18000000,18225000,18432000,18662400,18750000,18874368,18895680,18984375,19131876,19200000,19440000,19531250,19660800,19683000,19906560,20000000,20155392,20250000,20480000,20503125,20736000,20971520,20995200,21093750,21233664,21257640,21600000,21870000,22118400,22143375,22394880,22500000,22674816,22781250,23040000,23328000,23437500,23592960,23619600,23887872,23914845,24000000,24300000,24576000,24603750,24883200,25000000,25165824,25194240,25312500,25509168,25600000,25920000,26214400,26244000,26542080,26572050,26873856,27000000,27337500,27648000,27993600,28125000,28311552,28343520,28697814,28800000,29160000,29296875,29491200,29524500,29859840,30000000,30233088,30375000,30720000,31104000,31250000,31457280,31492800,31640625,31850496,31886460,32000000,32400000,32768000,32805000,33177600,33554432,33592320,33750000,34012224,34171875,34560000,34992000,35156250,35389440,35429400,35831808,36000000,36450000,36864000,36905625,37324800,37500000,37748736,37791360,37968750,38263752,38400000,38880000,39062500,39321600,39366000,39813120,39858075,40000000,40310784,40500000,40960000,41006250,41472000,41943040,41990400,42187500,42467328,42515280,43046721,43200000,43740000,44236800,44286750,44789760,45000000,45349632,45562500,46080000,46656000,46875000,47185920,47239200,47775744,47829690,48000000,48600000,48828125,49152000,49207500,49766400,50000000,50331648,50388480,50625000,51018336,51200000,51840000,52428800,52488000,52734375,53084160,53144100,53747712,54000000,54675000,55296000,55987200,56250000,56623104,56687040,56953125,57395628,57600000,58320000,58593750,58982400,59049000,59719680,60000000,60466176,60750000,61440000,61509375,62208000,62500000,62914560,62985600,63281250,63700992,63772920,64000000,64800000,65536000,65610000,66355200,66430125,67108864,67184640,67500000,68024448,68343750,69120000,69984000,70312500,70778880,70858800,71663616,71744535,72000000,72900000,73728000,73811250,74649600,75000000,75497472,75582720,75937500,76527504,76800000,77760000,78125000,78643200,78732000,79626240,79716150,80000000,80621568,81000000,81920000,82012500,82944000,83886080,83980800,84375000,84934656,85030560,86093442,86400000,87480000,87890625,88473600,88573500,89579520,90000000,90699264,91125000,92160000,93312000,93750000,94371840,94478400,94921875,95551488,95659380,96000000,97200000,97656250,98304000,98415000,99532800,100000000,100663296,100776960,101250000,102036672,102400000,102515625,103680000,104857600,104976000,105468750,106168320,106288200,107495424,108000000,109350000,110592000,110716875,111974400,112500000,113246208,113374080,113906250,114791256,115200000,116640000,117187500,117964800,118098000,119439360,119574225,120000000,120932352,121500000,122880000,123018750,124416000,125000000,125829120,125971200,126562500,127401984,127545840,128000000,129140163,129600000,131072000,131220000,132710400,132860250,134217728,134369280,135000000,136048896,136687500,138240000,139968000,140625000,141557760,141717600,143327232,143489070,144000000,145800000,146484375,147456000,147622500,149299200,150000000,150994944,151165440,151875000,153055008,153600000,155520000,156250000,157286400,157464000,158203125,159252480,159432300,160000000,161243136,162000000,163840000,164025000,165888000,167772160,167961600,168750000,169869312,170061120,170859375,172186884,172800000,174960000,175781250,176947200,177147000,179159040,180000000,181398528,182250000,184320000,184528125,186624000,187500000,188743680,188956800,189843750,191102976,191318760,192000000,194400000,195312500,196608000,196830000,199065600,199290375,200000000,201326592,201553920,202500000,204073344,204800000,205031250,207360000,209715200,209952000,210937500,212336640,212576400,214990848,215233605,216000000,218700000,221184000,221433750,223948800,225000000,226492416,226748160,227812500,229582512,230400000,233280000,234375000,235929600,236196000,238878720,239148450,240000000,241864704,243000000,244140625,245760000,246037500,248832000,250000000,251658240,251942400,253125000,254803968,255091680,256000000,258280326,259200000,262144000,262440000,263671875,265420800,265720500,268435456,268738560,270000000,272097792,273375000,276480000,279936000,281250000,283115520,283435200,284765625,286654464,286978140,288000000,291600000,292968750,294912000,295245000,298598400,300000000,301989888,302330880,303750000,306110016,307200000,307546875,311040000,312500000,314572800,314928000,316406250,318504960,318864600,320000000,322486272,324000000,327680000,328050000,331776000,332150625,335544320,335923200,337500000,339738624,340122240,341718750,344373768,345600000,349920000,351562500,353894400,354294000,358318080,358722675,360000000,362797056,364500000,368640000,369056250,373248000,375000000,377487360,377913600,379687500,382205952,382637520,384000000,387420489,388800000,390625000,393216000,393660000,398131200,398580750,400000000,402653184,403107840,405000000,408146688,409600000,410062500,414720000,419430400,419904000,421875000,424673280,425152800,429981696,430467210,432000000,437400000,439453125,442368000,442867500,447897600,450000000,452984832,453496320,455625000,459165024,460800000,466560000,468750000,471859200,472392000,474609375,477757440,478296900,480000000,483729408,486000000,488281250,491520000,492075000,497664000,500000000,503316480,503884800,506250000,509607936,510183360,512000000,512578125,516560652,518400000,524288000,524880000,527343750,530841600,531441000,536870912,537477120,540000000,544195584,546750000,552960000,553584375,559872000,562500000,566231040,566870400,569531250,573308928,573956280,576000000,583200000,585937500,589824000,590490000,597196800,597871125,600000000,603979776,604661760,607500000,612220032,614400000,615093750,622080000,625000000,629145600,629856000,632812500,637009920,637729200,640000000,644972544,645700815,648000000,655360000,656100000,663552000,664301250,671088640,671846400,675000000,679477248,680244480,683437500,688747536,691200000,699840000,703125000,707788800,708588000,716636160,717445350,720000000,725594112,729000000,732421875,737280000,738112500,746496000,750000000,754974720,755827200,759375000,764411904,765275040,768000000,774840978,777600000,781250000,786432000,787320000,791015625,796262400,797161500,800000000,805306368,806215680,810000000,816293376,819200000,820125000,829440000,838860800,839808000,843750000,849346560,850305600,854296875,859963392,860934420,864000000,874800000,878906250,884736000,885735000,895795200,900000000,905969664,906992640,911250000,918330048,921600000,922640625,933120000,937500000,943718400,944784000,949218750,955514880,956593800,960000000,967458816,972000000,976562500,983040000,984150000,995328000,996451875,1000000000,1006632960,1007769600,1012500000,1019215872,1020366720,1024000000,1025156250,1033121304,1036800000,1048576000,1049760000,1054687500,1061683200,1062882000,1073741824,1074954240,1076168025,1080000000,1088391168,1093500000,1105920000,1107168750,1119744000,1125000000,1132462080,1133740800,1139062500,1146617856,1147912560,1152000000,1162261467,1166400000,1171875000,1179648000,1180980000,1194393600,1195742250,1200000000,1207959552,1209323520,1215000000,1220703125,1224440064,1228800000,1230187500,1244160000,1250000000,1258291200,1259712000,1265625000,1274019840,1275458400,1280000000,1289945088,1291401630,1296000000,1310720000,1312200000,1318359375,1327104000,1328602500,1342177280,1343692800,1350000000,1358954496,1360488960,1366875000,1377495072,1382400000,1399680000,1406250000,1415577600,1417176000,1423828125,1433272320,1434890700,1440000000,1451188224,1458000000,1464843750,1474560000,1476225000,1492992000,1500000000,1509949440,1511654400,1518750000,1528823808,1530550080,1536000000,1537734375,1549681956,1555200000,1562500000,1572864000,1574640000,1582031250,1592524800,1594323000,1600000000,1610612736,1612431360,1620000000,1632586752,1638400000,1640250000,1658880000,1660753125,1677721600,1679616000,1687500000,1698693120,1700611200,1708593750,1719926784,1721868840,1728000000,1749600000,1757812500,1769472000,1771470000,1791590400,1793613375,1800000000,1811939328,1813985280,1822500000,1836660096,1843200000,1845281250,1866240000,1875000000,1887436800,1889568000,1898437500,1911029760,1913187600,1920000000,1934917632,1937102445,1944000000,1953125000,1966080000,1968300000,1990656000,1992903750,2000000000,2013265920,2015539200,2025000000,2038431744,2040733440,2048000000,2050312500,2066242608,2073600000,2097152000,2099520000,2109375000,2123366400,2125764000};
int main(){
    int n;
    cin >> n;
    cout << f[n] << endl;
    return 0;
}

算法二(多路归并)

因为 N = 2 a 3 b 5 c N = 2^a3^b5^c N=2a3b5c,所以 n n n一定是若干个2、3、5相乘,可以理解为求只由三个质数2、3、5组成的数,从小到大排列,根据上题分析，所有满足条件的数不超过 8000 8000 8000个,因此可以使用三个指针 i 、 j 、 k i、j、k i、j、k维护第 n n n个满足条件的数,时间复杂度 O ( n ) O(n) O(n)

代码如下：

有个细节，那就是循环中不使用else if而是使用if，那是为了避免重复(例如 2 ∗ 3 = 3 ∗ 2 2*3 = 3*2 2∗3=3∗2)， 所以将所有等于now的值的指针都往后移动一位。

#include
using namespace std;
int f[8001];
int main(){
    int n;
    cin >> n;
    int i = 1, j = 1, k = 1, now = 1, idx = 1;
    f[1] = 1;
    while(--n){
        f[++idx] = now = min(min(f[i] * 2, f[j] * 3), f[k] * 5);
        if(f[i] * 2 == now) i++;
        if(f[j] * 3 == now) j++;
        if(f[k] * 5 == now) k++;
    }
    cout << now;
    return 0;
}