丑数与非丑数

18005It 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

丑数就是仅包含2,3,5的数。一个数n可以分解为l个2,n个3，m个5（n,m,l为任意数）

也就是可以通过任意的除以2，除以3，除以5，最后得到1！

1,2,3,4,5均是丑数

while(n!=1)

{

if(n%2!=0||n%3!=0||n%5!=0)

break;

if(n%2==0)

n=n/2;

if(n%3==0)

n=n/3;

if(n%5==0)

n=n/5;

}

if(n==1)

cout<<"YES"<

else

cout<<"NO"<

接下来计算非丑数

#include
#include
using namespace std;
typedef pair node_type;
int main()
{
unsigned long result[1500];
priority_queue< node_type, vector, greater > Q;
//此处的greater是小顶对，就是队头一直保持为最小权值
Q.push(node_type(1, 2));
for (int i = 0; i < 1500; i++)
{
node_type node = Q.top();
Q.pop();
switch (node.second)
{
case 2:
Q.push(make_pair(node.first * 2, 2));
case 3:
Q.push(make_pair(node.first * 3, 3));
case 5:
Q.push(make_pair(node.first * 5, 5));
}//由于没有break因此，会一直

//因此队列中的元素会非常多,因此只需要继续赋值即可以继续得到丑数
result[i] = node.first;
}
/*int i;//能计算1500个丑数
for(i=0;i<1500;i++)
cout< int T;
cin >> T;
while (T--)
{
int n;//n表示要求第n个数
int f = 0;//f用于记录已经找到了多少个非丑数
cin >> n;
unsigned long i, k, d;//k用来记录时找到的丑数的值
for (i = 0; i < 1500; i++)
{
d = result[i + 1] - result[i];//两个数的间隔，判断中间是否有非丑数
if (d > 1)
{
d--;
if (f + d < n)//如果累计还没达到第n个非丑数，继续前进
{
f += d;
//k = result[i + 1] - 1;
}
else
{
k = result[i] + n - f;
break;
}
}
}
cout << k << endl;
}
return 0;
}
//数学运算经常需要把单位去掉，然后一起运算，比如类标的数组,这样反而能很好的表示逻辑
//在此处的数组下标与数组元素的值就是典型的单位不同的情况。

//计算智能此题的目的为了解stl的使用,所以故意用来很多的stl容器

;*>;*>