醜數
Ugly Number 的定義為:該數之質因數只能有 2 或 3 或 5,不能有其他的質因數。
當然了,依照慣例,1 也算是 Ugly Number。
在此列舉一串數列:1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,這些就是前 11 個 UglyNumbers。
請寫一個程式求出第 N 個 Ugly Number。
Input
第一行為測資筆數 K
第二行開始為正整數 N, N <= 1000
Output
每行一個,輸出 K 行
第 N 個 Ugly Number
範例輸入:
3
7
11
150
範例輸出:
8
15
5832
/*----- ----- ----- -----*/ //3-Ugly Numbers //Made by 105502555 Teemo Hsu(Synasaivaltos) //Date: 2018/03/21 /*----- ----- ----- -----*/ #include <iostream> #include <queue> #include <vector> using namespace std; int main(void) { int n; cin >> n; vector<long long> ans; long long un; priority_queue<long long> next_un; while(--n>=0) { int m; cin >> m; un=1; for(int i=1;i<m;i++) { next_un.push(-un*2); next_un.push(-un*3); next_un.push(-un*5); while(-next_un.top()==un) next_un.pop(); un=-next_un.top(); next_un.pop(); } ans.push_back(un); } for(int i=0;i<ans.size();cout<<ans.at(i)<<endl,i++); return 0; } |