作者cismjmgoshr (--？？？--)
看板C_and_CPP
标题Re: [ACM ] 136如何优化速度
时间Fri Feb 20 21:35:17 2009
我的想法是这样:
ugly number只有2,3,5三个质因数
所以任两个ugly number相乘的结果也是ugly number
任一个ugly number分成两个数字的乘积时,两个数也都是ugly number
因此,第k个ugly number必为第1~(k-1)个ugly number其中两个的乘积
所以,第k个ugly number是 第1~(k-1)个ugly number,任取两个相乘後,值最小的那一个数
这样可以不用从1开始一个一个数检查
--
∫work dt = success
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.193.177
※ 编辑: cismjmgoshr 来自: 61.230.193.177 (02/20 21:36)
1F：→ Holocaust123:好厉害，DP耶! 02/20 21:38
2F：→ bleed1979:嗯 我在2,3,5,7的那题是用这个方法 02/21 01:19