丑数与非丑数
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 sequence 1, 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容器