POJ 1338 Ugly Numbers

Ugly Number可以表示为 [i, j, k] ， i,j,k 分别表示 2 3 5 因子的个数；

估计一下 i<=12 j <= 12, k<=12内有超过2000个，30^12 < 2^60，在long long 以内；

关键是要按大小次序来，DISCUSS中有个大牛提了个很好的方法，我是按照他的方法来写的，0MS。

# include <stdio.h>

# define MIN(x, y) ((x)<(y) ? (x):(y)) 

long long t[1505];

int main()
{
    int i, j, k, p;

    t[0] = 1;
    i = j = k = 0;
    for (p = 1; p < 1505; ++p)
    {
        t[p] = MIN(t[i]*2, MIN(t[j]*3, t[k]*5));
        if (t[p] == t[i]*2) ++i;
        if (t[p] == t[j]*3) ++j;
        if (t[p] == t[k]*5) ++k;
    }
    
    while (~scanf("%d", &p) && p)
        printf("%lld\n", t[p-1]);

    return 0;
}