题解 P2723 【丑数 Humble Numbers】

· · 题解

网上题解+下面大神的题解

为了找第i个丑数，那么一定要比第i-1个丑数大，而且是最小的那一个，可以发现比i-1大的丑数一定是比i-1小的丑数乘某个质数得到的，鉴于质数的数量很少，而丑数的数量很大，我们枚举质数，然后枚举丑数，直到大于第i-1个丑数，记录一下，找到所有的符合条件的丑数以后，找出最小值（也可以在寻找的途中更新最小值），那么这个最小值就是第i个丑数。

#include<cstdio>
    int n,m;
    int a[101],b[101];
    int s[100001];
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    s[0]=1;
    for(int i=1;i<=m;i++)
    {
        int min=2147483647;
        for(int j=1;j<=n;j++)
        {
            while(a[j]*s[b[j]]<=s[i-1]) b[j]++;
            if(a[j]*s[b[j]]<min) min=a[j]*s[b[j]];
        }
        s[i]=min;
    }
    printf("%d",s[m]);
}