首页 > 代码库 > Ugly Numbers(1.5.8)
Ugly Numbers(1.5.8)
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.
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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。