丑数(Ugly Numbers, UVa 136)

我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。

1. 版本1：错误版本

//#define LOCAL#include#include#includeusing namespace std;typedef long long LL;
const int coeff[3]={2,3,5};int main(){    
#ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);    
    #endif

    priority_queue,greater > pq;//!1
    pq.push(1);//初始化得有1个1.
    for(int i=1;;i++){        //每次循环都从pq中取出一个丑数，根据这个丑数计算出新的丑数，并注入。
        LL ugly=pq.top();
        pq.pop();        
        if(i==1500){cout<
以上思路是通过每次从优先队列pq中获取一个丑数，然后通过这个丑数计算出新的丑数，对于任意的丑数x，他的2，3，5倍也都是丑数，通过这样的方法，可以把所有的丑数一网打尽。
但是这个地方没有考虑周全的是，不同的生成方法可能会生成同一个丑数，所以里面肯定有许多次重复了，比如235=325=532=...，所以需要一个数据结构来记录丑数是不是已经出现过了，set集合挺适合的，那么修改代码后如下。
//#define LOCAL
#include
#include
#include
#includeusing namespace std;typedef long long LL;const int coeff[3]={2,3,5};int main(){    
#ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);    
    #endif

    priority_queue,greater > pq;//!1
    set s;
    pq.push(1);//初始化得有1个1.
    s.insert(1);    
    for(int i=1;;i++){        //每次循环都从pq中取出一个丑数，根据这个丑数计算出新的丑数，并注入。
        LL ugly=pq.top();
        pq.pop();        if(i==1500){cout<
keep going
作者：MarkKobs
原文链接：https://www.cnblogs.com/MarkKobs-blog/p/10460342.html