题目大意

丑数列是一个元素质因子仅包含 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