【题解】丑数Humble Numbers-C++

题目描述
Description
对于一给定的素数集合 S = {p1, p2, …, pK},如果一个数字，当我们对其做完质因子分解后，其质因子全是来自我们给定的素数集合，则认为这个数字是个丑数。
注意：我们不认为1 是一个丑数。
你的工作是对于输入的集合S去寻找第N个丑数。
Input
第 1 行: 二个被空间分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000.
第 2 行: K 个被空间分开的整数:集合S的元素
Output
第N个丑数。
Sample Input
4 19
2 3 5 7
Sample Output
27

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

代码

#include<bits/stdc++.h>
using namespace std; 
int n,m;
int a[101],b[101],s[100001]={1};
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int minn=0x7f7f7f7f;
        for(int j=1;j<=n;j++)
        {
            while(a[j]*s[b[j]]<=s[i-1])
            {
                b[j]++;
            }
            if(a[j]*s[b[j]]<minn)
        minn=a[j]*s[b[j]];
        }
        s[i]=minn;
    }
    cout<<s[m]<<endl;
    return 0;
}