首页 > 代码库 > Ugly Numbers(1.5.8)

Ugly Numbers(1.5.8)

2024-07-12 18:02:51   220人阅读

Ugly Numbers(1.5.8)

Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64

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.
Given the integer n,write a program to find and print the n‘th ugly number.

Input

Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.

Output

For each line, output the n’th ugly number .:Don’t deal with the line with n=0.

Sample Input

1290

Sample Output

1210
题意：
把质因子只有2,3,5的数称为Ugly数，求第k大的Ugly数。（1是第一个）
思路：
定义优先队列，数越小优先级越高，先出队列，然后*2 *3 *5进队列（注意消去重复的数）
#include<stdio.h>#include<iostream>#include<queue>using namespace std;#define ll __int64struct node  {	ll num;	friend bool operator < (const node &a,const node &b)//定义优先级	{		return a.num>b.num;	}};ll bfs(ll n) {	ll sum;	node x,y,z;	sum=0;	priority_queue<node>que;		x.num=1;z.num=0; 		que.push(x);// 1进队列	while(1)	{		x=que.top();		que.pop();//优先级最高的先出队列		if(x.num==z.num) continue;//与之前重复的数不计		sum++;		if(sum==n) return x.num;//找到第n个		y.num=x.num*2;		que.push(y);		y.num=x.num*3;		que.push(y);		y.num=x.num*5;		que.push(y);		z.num=x.num;	}	return 0;}int main(){	ll num;	while(scanf("%I64d",&num)&&num)	{		printf("%I64d\n",bfs(num));	}	return 0;}


联系
我们