P2723 丑数 Humble Numbers

题意：给你k个质数，定义丑数集合为k个质数随机（1--k）个相乘得到的数

　　　求第n小的丑数

暴力。。。貌似不太可行，（把所有大量丑数求出来，sort   QAQ）

可以想到，对于第i个丑数f[i]，它一定是由之前的某个丑数*a[i]得到的

所以枚举之前已求出的丑数和a[i]相乘若>f[i-1] 则与ans取min

这些大于f[i-1]的所有值的min就是f[i]！(f[i]是大于f[i-1]的第一个数）

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define int long long

#define olinr return

#define _ 0

#define love_nmr 0

#define DB double

inline int read()

{

    int x=,f=;

    char ch=getchar();

    while(!isdigit(ch))

    {

        if(ch=='-')

            f=-f;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    return x*f;

}

inline void put(int x)

{

    if(x<)

    {

        x=-x;

        putchar('-');

    }

    if(x>)

        put(x/);

    putchar(x%+'');

}

int n;

int k;

int a[];

int f[];

int s[];

signed main()

{

    k=read();

    n=read();

    f[]=;

    for(int i=;i<=k;i++)

        a[i]=read();

    for(int i=;i<=n;i++)

    {

        int ans=0x7fffffff;

        for(int j=;j<=k;j++)

        {

            int l=,r=i-;

            int t=;

            while(l<=r)

            {

                int mid=(l+r)>>;

                if(a[j]*f[mid]<=f[i-])

                {

                    l=mid+;

                }

                else

                {

                    r=mid-;

                    t=mid;

                }

            }

            ans=min(ans,f[t]*a[j]);

        }

        f[i]=ans;

    }

    put(f[n]);

    olinr ~~(^_^)+love_nmr;

}