紫薯 例题5-7

一、题意

输出从小到大排列的第1500个丑数。
丑数定义：不能被2，3，5以外的其它素数整除的数。

二、解析

不能被其它素数整除，也就是说丑数质因子分解后只有2，3，5,所以丑数就是有这三个数的乘积组成的。用一个优先队列维护已经求出的最小丑数。从1开始，每次从优先队列中取出当前最小的丑数，然后将它的2，3，5倍放入队列中，来扩充丑数序列，注意队列中已经存在的数就不要重复放了，因此还需要用一个set来记录队列中是否已经存在某个数了。

三、代码

#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;
using LL = long long;
const int k[3] = {2, 3, 5};
priority_queue<LL, vector<LL>, greater<LL> > q;
set<LL> ans;
int n = 1500;
LL x;

int main() {
    q.push(1);
    ans.insert(1);
    while(n --) {
        x = q.top();
        q.pop();
        for(int i = 0; i < 3; i ++) {
            LL m = x * k[i];
            if(!ans.count(m)) q.push(m), ans.insert(m);
        }
    }
    cout << "The 1500'th ugly number is " << x << "." << endl;
}

归纳

  • 优先队列priority_queue、集合set的应用
  • 做题时要注意数字范围，有时要用LL

想当年这道题卡了好久...应该是做的第3次了，终于有点进步的感觉了2333