P2723 丑数 Humble Numbers

挺好的一道题。

我只想到了用 $1-n-1$ 的丑数依次生成丑数，用优先队列来找最小的做法。

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#define mk(a) ((L){a})
#define inf 2147483647LL
#define ll long long int
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int maxn=111111;
struct L{
    ll x;
    bool operator < (const L &b)const{
        return x>b.x;
    }
};
priority_queue <L> qu;

int k,n;
ll p[maxn];
int main(){
    cin>>k>>n;
    rep(i,1,k)cin>>p[i],qu.push(mk(p[i]));
    rep(i,1,n-1){
        ll x=qu.top().x;//cout<<x<<endl;
        while(qu.top().x==x)qu.pop();//去重
        rep(j,1,k)qu.push(mk(x*p[j]));
    }
    cout<<qu.top().x;
    return 0;
}

然而这样生成的丑数太多了。实际上，光是 $n*k$ 就已经接近时限了。

实际上，我们只需要用到 $1-n$ 的丑数，后面过大的没有必要生成。

但每次暴力找到当前丑数所能生成的最小新丑数是 $O(n^2k)$ 的。

然后我们发现，找最小新丑数具有两个单调性。

$1:$ 对于每个丑数，其用到的质数是单调增的。

$2:$ 对于v每个质数，其用到的丑数也是单调增的。

使用第一个单调性的复杂度是 $O(n^2+nk)$ ，第二个是 $O(k^2+nK)$ 。

显然我们只要使用第二个单调性就可以解决此题。

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long int
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int maxn=111111;

int k,n;
ll p[maxn],f[maxn],cur[maxn];//cur记录当前p所用到的最大丑数
int main(){
    scanf("%d%d",&k,&n);
    rep(i,1,k)scanf("%lld",&p[i]);
    memset(cur,0,sizeof(cur));
    f[0]=1;
    rep(i,1,n){
        ll mi=4000000000LL;
        rep(j,1,k){
            while(p[j]*f[cur[j]]<=f[i-1])cur[j]++;
            if(p[j]*f[cur[j]]<mi)mi=p[j]*f[cur[j]];
        }
        f[i]=mi;
    }
    cout<<f[n];
    return 0;
}