f250 - ugly ++
題目描述
題目要求計算第 n 個醜數。醜數的定義是只能由 2, 3, 5 三個質因數組成的正整數。給定 t 個查詢，每個查詢輸入一個正整數 n，輸出第 n 個醜數。
解題思路
由於 n 的範圍不大 (0 < n <= 10^4)，且題目給定的 u[10000] < 10^18 的條件，可以採用暴力法生成所有醜數，然後進行排序，最後根據查詢的 n 值輸出對應的醜數。
生成醜數的方法是通過三重循環，分別遍歷 2, 3, 5 的冪次，將所有可能的醜數生成並存儲在一個數組中。
生成完所有醜數後，使用 sort 函數對數組進行排序。
最後，對於每個查詢，直接從排序後的數組中取出第 n 個元素即可。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是生成的醜數的數量。三重循環生成醜數的時間複雜度可以近似看作 O(N)，排序的時間複雜度為 O(N log N)。
- 空間複雜度: O(N)，用於存儲生成的醜數。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
long long int ans[11001],it,t,n;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(long long int i=1;i<1000000000000000000;i*=2){
for(long long int j=1;i*j<1000000000000000000;j*=3){
for(long long int k=1;i*j*k<1000000000000000000;k*=5){
ans[it]=i*j*k;
++it;
}
}
}
sort(ans,ans+it);
cin >> t;
while(t--){
cin >> n;
cout << ans[n-1] << '\n';
}
}