18005 它不是丑数
| 题型: 编程题 语言: G++;GCC Description“丑数”是指除了质因子2,3，5，不含其它质因子的正整数，例如由小到大前10个“丑数”为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ... 非“丑数”的前10个数为 7, 11, 13, 14, 17, 19, 21, 22, 23, 26, ... 现要求编写一个程序，输出指定第几位的非“丑数”。 输入格式第一行为正整数T（T<=10000）, 表示case的数目。 此后T行，每行一个正整数 n (n <= 100000000). 输出格式每一个n，输出第n个非“丑数” 输入样例3 1 2 9 输出样例7 11 23 |
题意：
求第n个非丑数
分析：
暴力求解，我们只要求出是丑数的数，那么非丑数就是在丑数和丑数之间了。
吐槽一下，学校oj开1e8+5明明就够了，就是不让过，搞得我搞了半个多小时在找bug
没想到居然得开再大点才过得了，服了
//我用的是紫书上优先队列的方法写的，详细解释可以看我的博客紫书上的丑数，里面有详解
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=200000005;
ll a[N];
int nums[3]={2,3,5};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t,cnt=0;
cin>>t;
priority_queue<ll,vector<ll>,greater<ll> >q;
set<ll>s;
ll tmp=1,m=1;
q.push(1);
s.insert(1);
while(cnt<=100000000){
tmp=m;
m=q.top();
q.pop();
for(ll i=tmp+1;i<m;++i){
a[++cnt]=i;
//cout<<a[cnt]<<endl;
}
for(int i=0;i<3;++i){
ll x=nums[i]*m;
if(!s.count(x)){
s.insert(x);
q.push(x);
}
}
}
while(t--){
int n;
cin>>n;
cout<<a[n]<<endl;
}
return 0;
}