首先題目給出一個(gè)定義，一個(gè)數(shù)具有productive property是指這個(gè)數(shù)是另一個(gè)數(shù)所有位上數(shù)字的乘積。如2是12各位上數(shù)字的乘積，80也是：80=2*2*2*5。
題目要求給出一個(gè)正整數(shù)i，求出按升序排列后第i個(gè)具有productive property的數(shù)是多少。題目保證結(jié)果不會(huì)大于10^18。
最直接的想法就是找出所有這樣的數(shù)，然后排序，按i輸出相應(yīng)的數(shù)。

這里我走了一條彎路，一開始是想找出所有的數(shù)，這些數(shù)沒有大于10的質(zhì)因子，但這樣就要打素?cái)?shù)表，還要對(duì)一個(gè)數(shù)進(jìn)行試除，時(shí)間復(fù)雜度比較高（從10試到10^18）。

其實(shí)反過來想，時(shí)間復(fù)雜度可以大大降低：這些數(shù)的因子只能是2,3,5,7，由這些因子所產(chǎn)生的合數(shù)數(shù)目肯定大大小于10^18。
簡(jiǎn)單計(jì)算一下可以知道：2^59<10^18, 3^37<10^18, 5^25<10^18, 7^21<10^18。因此只要產(chǎn)生59*37*25*21<=1146075個(gè)數(shù)就夠了。

如何高效產(chǎn)生這些數(shù)呢？這里使用了類似DFS+剪枝的技術(shù)，設(shè)當(dāng)前這個(gè)數(shù)為tmp, 則若tmp*c>10^18就不用再乘下去了，其中c是2,3,5,7其中某個(gè)數(shù)的冪次。具體見程序里的 init

#include <iostream>
#include <algorithm>

using namespace std;

__int64 b=1;
__int64 a[1146075];
__int64 f[4][60];
void init()
{
    // i,j,k,l分別是2,3,5,7的冪次
    int i,j,k,l,cnt=0;
    // 預(yù)先計(jì)算階乘
    b=1;
    for(i=1;i<=18;i++) b*=10;
    f[0][0]=f[1][0]=f[2][0]=f[3][0]=1;
    for(i=1;i<=59;i++) f[0][i]=f[0][i-1]*2;
    for(i=1;i<=37;i++) f[1][i]=f[1][i-1]*3;
    for(i=1;i<=25;i++) f[2][i]=f[2][i-1]*5;
    for(i=1;i<=21;i++) f[3][i]=f[3][i-1]*7;
    // 產(chǎn)生所有質(zhì)因子在10以內(nèi)的數(shù)
    __int64 tmp;
    for(i=0;i<=59;i++){
        tmp=f[0][i];
        for(j=0;j<=37;j++){
            if(tmp*f[1][j]>=b) break;
            else tmp*=f[1][j];
            for(k=0;k<=25;k++){
                if(tmp*f[2][k]>=b) break;
                else tmp*=f[2][k];
                for(l=0;l<=21;l++){
                    if(tmp*f[3][l]>=b) break;
                    else a[cnt++]=tmp*f[3][l];
                }
                tmp/=f[2][k];
            }
            tmp/=f[1][j];
        }
        tmp/=f[0][i];
    }
    sort(a,a+cnt);
}

int main()
{
    init();
    int t,i;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&i);
        printf("%I64d\n",a[i-1]);
    }
    return 1;
}