Problem 3992 --Ugly Number

3992: Ugly Number

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $15$ 正确数量 $5$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
一个整数N(N<=100000)
第N个丑数 特别的,我们规定第一个丑数是1
10
12
  1. The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
  2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
  3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
  4. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

推荐代码 查看3992 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$2 $ms] thisislike 994809 2023-09-25 21:24:21
内存最少[$2380 $KB] thisislike 994809 2023-09-25 21:24:21
第一AC AOJ大管家 832989 2022-04-02 21:53:15
第一挑战 AOJ大管家 832978 2022-04-02 21:44:00

赛题来源/所属竞赛 2022年大学生程序设计竞赛网络赛本专科组 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛