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也是同樣道理。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	unsigned long long int N[1501];
	N[1]=1;
	int p2=1,p3=1,p5=1;
	for (int n=2; n<=1500; n++){
	while (N[p2]*2 <= N[n-1]) p2++;
	while (N[p3]*3 <= N[n-1]) p3++;
	while (N[p5]*5 <= N[n-1]) p5++;
	N[n] = min (N[p2]*2, min (N[p3]*3, N[p5]*5));
	}
	printf("The 1500'th ugly number is %llu.\n",N[1500]);
	}

view raw [UVa] 136 Ugly Number.cpp hosted with ❤ by GitHub