codevs1246 丑数

题目描述 Description

对于一给定的素数集合 S = {p1, p2, ..., pK},
来考虑那些质因数全部属于S 的数的集合。这个集合包括，p1, p1p2, p1p1, 和 p1p2p3 (还有其它)。这是个对于一个输入的S的丑数集合。
注意：我们不认为1 是一个丑数。
你的工作是对于输入的集合S去寻找集合中的第N个丑数。longint(signed 32-bit)对于程序是足够的。

输入描述 Input Description

第 1 行: 二个被空间分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000.
第 2 行: K 个被空间分开的整数:集合S的元素

输出描述 Output Description

单独的一行，写上对于输入的S的第N个丑数。

样例输入 Sample Input

4 19
2 3 5 7

样例输出 Sample Output

数据范围及提示 Data Size & Hint

----------分界线----------

我们可以发现所有S中的数都满足如下规律：

Si>Sj(j<i)

Si都是S1~Si-1中的某一个数程P中某一个数的结果

Si是满足上述两条中的最小的一个

这样计算Si时可以枚举P，然后二分查找一个恰当的S（S是严格上升的）

这样一直计算到n即可。

让S0=1，这样P中的数字可以乘以这个1来直接加入到S

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define debug(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

int k,n;
long long p[105],s[100005];

int main(){
    memset(s,0x7f,sizeof(s));
    
    cin>>k>>n;
    for(int i=1;i<=k;i++){
        cin>>p[i];
    }
    s[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            //er fen
            int l=0,r=i-1,mid;
            while(l<r){
                mid=(l+r)/2;
                if(s[mid]*p[j]>s[i-1])r=mid;
                else l=mid+1;
            }
            s[i]=min(s[i],p[j]*s[r]);
        }
//        debug(i); debug(s[i]);
    }
    cout<<s[n]<<endl;

    return 0;
}

相关推荐