Uva 136 - Ugly Number

題目

Problem

Ulgy Number是只有$2$、$3$、$5$質因數的數字。前11項是:
$$
1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 12,\ 15,\ …
$$
程式必須印出第1500項ugly number

想法

第$n$個數字一定是前$n-1$個數字中,乘$2$、乘$3$、乘$5$得來的。
找數字的時候不用每個都從頭開始找,要找第$n$個數字,而這個數字勢必$>$第${n-1}$個數字,所以第i, j, k個數字(分別乘$2$、乘$3$、乘$5$),至少要$>$第$n-1$個數字才有可能成為第$n$個數字。在這三種可能中,挑最小的便是第$n$個數字。

AC Code

https://github.com/roy4801/solved_problems/blob/master/uva/136.cpp

推薦文章