题目大意

丑数列是一个元素质因子仅包含 2,3,5 的数列,特别地,1 包含在内。

1,2,3,4,5,6,8,10,12,15,\ldots

请输出第1500个丑数。

题目分析

由于质因数只包含 2,3,5 ,元素可以转化为 2^i\cdot 3^j\cdot 5^k,也就是说序列中的每个元素只要乘上 2,3,5 都可以生成后面的元素。只需每次找出这之中最小的一个去乘。

如果直接用小根堆维护,不会得到想要的答案。因为会有重复的元素。当生成某个元素的时候,别的系数就不应该生成该数,所以相应地,让别的系数理应乘上更大的数。

如何实现:维护三个变量,分别维护三种系数产生的值。每次从这三个数中找到最小的,让其加入数列,并乘上相应系数。同时维护三个指针 i,j,k,每次如果发现最小的值与另一个系数产生的值相同,就让这个相同的数变为其系数乘以指针后一位的数。(这点理解有些困难,好好体会)

Code

The 1500'th ugly number is 859963392.

话说UVA好像不支持php