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> using namespace std; int min3(int a,int b,int c) { int min=a>b?b:a; return min>c?c:min; } int main() { int min,*p,i,j,f2=0,f3=0,f5=0,n=1500,count; p=(int *)malloc(n*sizeof(int )); *p=1; for(i=1;i<n;i++) { min=min3(*(p+f2)*2,*(p+f3)*3,*(p+f5)*5); p[i]=min; if(min==*(p+f2)*2) f2++; if(min==*(p+f3)*3) f3++; if(min==*(p+f5)*5) f5++; } cin>>j; while(j--) { scanf("%d",&n); i=-1,count=0; while(i++,1) { count+=p[i+1]-p[i]-1; if(count>=n) break; } printf("%d\n",p[i+1]+n-count-1); } }