網頁

2014年1月29日 星期三

UVa 136 & POJ 1338 Ugly Number

想法:
  下一個數必定是從之前的某個數x2或x3或x5而來的,因此要找第n個數(N[n]),就把前n-1個數x2,x3,x5,找出大於(N[n-1])的最小值。
  另外找第n個數的時候,乘以2不用每次都從第0個開始乘,每次紀錄2乘到哪個位置,以後就從這個位置往後找即可。例如12是從6這個數字乘以2而來,那麼要找12以後的number的時候,只要從6以後的數字乘以2開始找,因為6以前的數字乘以2不可能大於12,乘以3和乘以5也是同樣道理。