18005 It is not ugly number

﹏ヽ暗。殇╰゛Y 2022-09-22 15:51 10阅读 0赞

# 18005 It is not ugly number #

时间限制:2000MS  内存限制:65535K  
提交次数:0 通过次数:0

题型: 编程题   语言: G++;GCC

# Description #

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...shows the 
    first 10 ugly numbers. By convention, 1 is included. Then, here are the first 10 Not ugly numbers:7, 11, 13, 14, 17, 19, 
    21, 22, 23, 26. Given the integer n, write a program to find and print the n'th Not ugly number.

# 输入格式 #

First line is T（T<=10000）, the number of cases.
    The T lines following. Each line of the input contains a positive integer n (n <= 100000000).

# 输出格式 #

For each case, output the n'th Not ugly number .

# 输入样例 #

3
    1
    2
    9

# 输出样例 #

# 7 11 23 #

#  #

# \#include <iostream> \#include <cstdio> \#include <cstdlib> \#include <cmath> \#include <string.h> \#include <algorithm> \#include <queue> \#include <stack> \#include <vector>  using namespace std;          int a\[1500\];   typedef pair<int,int> temp;   int main()   \{       int t,n,i,cnt=0;       priority\_queue<temp,vector<temp>,greater<temp> > pq;       temp tempp;       pq.push(temp(1,2));       for(i=0;i<1205;++i)\{           tempp=pq.top();           switch(tempp.second)\{               case 2:pq.push(temp(tempp.first\*2,2));               case 3:pq.push(temp(tempp.first\*3,3));               case 5:pq.push(temp(tempp.first\*5,5));           \}           a\[i\]=tempp.first;           pq.pop();       \}       scanf("%d",&t);       while(t--)\{           scanf("%d",&n);           cnt=0;           i=0;           while(cnt<n)\{               cnt+=a\[i+1\]-a\[i++\]-1;           \}           i--;           cnt-=a\[i+1\]-a\[i\]-1;           printf("%d\\n",a\[i\]+n-cnt);       \}       return 0;   \}      #