OJ Board

Unfortunately, there is no quick solution to this problem.

Backtracking with good cutoffs is probably efficient enough.

Note: Spoiler. If you want to solve this question by yourself, don't look at this now. O(n^2): Every ugly number other than 1 has the property that it = 2,3, or 5 multiplied by some other ugly number. Therefore, what can be done is the following: Store a list of ugly numbers. To obtain the next ugly...

well, there is an O(n log n) method.

for n=1500, it should finish nearly instantly.

There is also a lazy O(n^2) method that should work pretty fast.

<font size=-1>[ This Message was edited by: chrismoh on 2001-12-28 09:26 ]</font>

Hi, I think I'll try 453 on my own, thanks anyway. for 10061, there are 2 parts: (1) Find number of trailing zeroes Factorize the base and the factorial. Actually you don't have to factorize the factorial completely. Just calculate the prime factors present in the base. e.g. in base 10, 10 = 2 * 5 1...

Nearly all C code can be compiled in C++, except for those using arcane constructs. I prefer gets and strtok to read until end of line. e.g. (to read numbers in one line) gets(buf); b = strtok(buf," -,;:"); /* whatever */ while (b) { some_variable = atoi(b); b = strtok(NULL," -,;:"); } strlen is slo...