d129: 00136 - Ugly Numbers

CPE 一顆星

題目連結:https://zerojudge.tw/ShowProblem?problemid=d129

內容

Ugly Number的定義為：該數之質因數必須為 2, 3 或 5
當然了，依照慣例，1 也算是 Ugly Number。
在此列舉一串數列：
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15
這些就是前 11 個 Ugly Numbers。
請寫一個程式求出第1500個Ugly Number。

範例輸入

No input

範例輸出

The 1500’th ugly number is .

想法

依序拿每個已知的 Ugly Number 去乘上2, 3, 5產生新的 Ugly Number。

從1開始，得到2, 3, 5，此時已知為1, 2, 3, 5。
接著拿2來乘，得到4, 6, 10，此時已知為1, 2, 3, 4, 5, 6, 10。
接著拿3，得到6, 9, 15，此時已知為1, 2, 3, 4, 5, 6, 9, 10, 15。
接著拿4，得到8, 12, 20，此時已知為1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20。
以此類推，直到產生第1500個 Ugly Number。

但是可能會遇到產生數字重覆的情況，像是拿2跟拿3來乘，6重複了。
以及數字大小順序問題，像是4產生的8比3產生的9, 15 還小。

此時可以運用 set 特性，不重複儲存相同的數，以及默認由小到大排列，即可解決問題。

使用 begin() 函數得到 set 內第一個元素，產生完新的數後可直接用 erase() 刪除，使得下一次使用 begin() 時為下一個數，紀錄刪了幾個數即可。

C++ STL: Set

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <bits/stdc++.h>
using namespace std;

int main(){
    int num[] = {2, 3, 5}, c = 0;
    set<long long> myset;
    long long temp;
    myset.insert(1);
    while(c < 1500){
        auto it = myset.begin();
        temp = *it;
        for(int i = 0; i < 3; ++i){
            myset.insert(temp*num[i]);
        }
        myset.erase(temp);
        ++c;
    }
    cout << "The 1500'th ugly number is " << temp << ".\n";

    return 0;
}