62.丑数
题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。
例如 6、8 都是丑数,但 14 不是,因为它包含质因子 7。
求第 n 个丑数的值。
题目链接
https://www.acwing.com/problem/content/description/58/
样例
in:5
out:5
分析:
1.“丑数”只能包含质因子2,3,5;
2.1也是丑数。
思路:
1.数据量很小,可以考虑枚举。
2.每一次不断地除以2,3,5,最后判断所枚举的数是否为1,注意不是0。
3.详情见AC代码!
code(严禁抄袭):
include [HTML_REMOVED]
define int long long//好习惯
using namespace std;
int _n;//第几个丑数
int _ans;//答案
int _cc;//记录当前扫到了几个
void ParseIn(){
cin >> _n;//输入
}
void Core(){
for(int i = 1; i <= 2147483647/当然会break掉/; i){
if(_cc == _n){//当以经找到 n个
break;
}
if(i == 1){//题目说了,1也是丑数
_cc ;
continue;
}
else{
int s = i;//防止改变i
while(s % 2 == 0){//去除质因子2
s /= 2;
}
while(s % 3 == 0){//去除质因子3
s /= 3;
}
while(s % 5 == 0){//去除质因子5
s /= 5;
}
if(s == 1){//但剩下1时
_cc ++;//累加,即又找到一个
_ans = i;//ans需要及时更新
}
}
}
}
void WriteOut(){
cout << _ans;//输出
}
signed main(){
ParseIn();
Core();
WriteOut();
return 0;
}
------废话分割线------
这是本蒟蒻的第一篇题解,多多支持~~~
大佬勿喷,有错的地方请指出~~~
%%%