POJ 1338 - Ugly Numbers

http://poj.org/problem?id=1338

概要

素因数が 2, 3, 5 のみの数を ugly number とする． 慣例により 1 も ugly number とする．

最初の10個の ugly number は 1, 2, 3, 4, 5, 6, 8, 10, 12 である．

n 番目の ugly number を答える．

制約

• n <= 1500

解法

ugly number は乗法について閉じていることを利用して 1500 番目までの ugly number を生成しておく．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main(void)
 6 {
 7   static const int N = 1500;
 8   vector<int> ugly(N);
 9   ugly[0] = 1;
10   int a = 0, b = 0, c = 0;
11   for (int i = 1; i < N; i++) {
12     ugly[i] = min(2*ugly[a], min(3*ugly[b], 5*ugly[c]));
13     if (ugly[i] == 2*ugly[a]) {
14       a++;
15     }
16     if (ugly[i] == 3*ugly[b]) {
17       b++;
18     } if (ugly[i] == 5*ugly[c]) {
19       c++;
20     }
21   }
22 
23   int n;
24   while (cin >> n && n != 0) {
25     cout << ugly[n-1] << endl;
26   }
27   return 0;
28 }