【题解】丑数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[],b[],s[]={};

 int main()

 {

     cin>>n>>m;

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

         cin>>a[i];

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

     {

         int minn=0x7f7f7f7f;

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

         {

             while(a[j]*s[b[j]]<=s[i-])

             {

                 b[j]++;

             }

             if(a[j]*s[b[j]]<minn)

         minn=a[j]*s[b[j]];

         }

         s[i]=minn;

     }

     cout<<s[m]<<endl;

     return ;

 }

巴特西

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

最新文章

热门文章