U E D R , A S I H C RSS

Ugly Numbers/문보창

소감

2005/02/18 Accepted 0:00.006 64
접근 방법을 바꾼후 쉽게 풀린 문제. 지수의 조합을 이용.

Ugly Number

~cpp 
// no136 - Ugly Numbers(a)
#include <iostream> 
#include <cstdlib>
#include <cmath>
using namespace std; 

const int MAX = 2000;
inline int comp(const void *i,const void *j) { return *(int *)i-*(int *)j; };

int main() 
{ 
	int num[MAX];
	int count = 0;
	int expo2, expo3, expo5;
	int MAX_INT = pow(2,31) - 1;

	for (expo5=0; expo5<13; expo5++)
	{
		for (expo3=0; expo3<19; expo3++)
		{
			for (expo2=0; expo2<30; expo2++)
			{
				if (expo5 + expo3 + expo2 > 29)
					break;
				if (pow(2,expo2) * pow(3,expo3) * pow(5,expo5) > MAX_INT
					|| pow(2,expo2) * pow(3,expo3) * pow(5,expo5) < 0)
					break;
				num[count++] = pow(2,expo2) * pow(3,expo3) * pow(5,expo5);
			}
		}
	}
	qsort(num, count, sizeof(int), comp);
	cout << "The 1500'th ugly number is " << num[1499] << ".\n";
	return 0;                                 
} 
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:20
Processing time 0.0113 sec