首页 > 代码库 > hdu 1058 Humble Numbers（构造？枚举？）
hdu 1058 Humble Numbers（构造？枚举？）
题意：
一个数的质因子如果只是2，3，5，7中的若干个。则这个数叫做humble number。
例如：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ...
给n，问第n个humble number是多少。
思路：
所有的humble数的构造都是：(2^a)*(3^b)*(5^c)*(7^d)。a,b,c,d大于等于0。
X=a+b+c+d代表这个数是第X个humble数。
假设前i-1个humble数已经求出来了，第i个humble数如何求呢？
一定是前i-1个humble数中的某个humble数乘以2或乘以3或乘以5或乘以7得到的。
好了，枚举前i-1个humble数，找出大于第i-1个humble数并且是最小，那么它就是第i个humble数了。
看代码
代码：
ll a[5850];int cn=0;int main(){ a[1]=1; cn=1; while(cn<5842){ ll ans=INF; ll temp; rep(i,1,cn){ temp=a[i]*2; if(temp>a[cn]) ans=min(ans,temp); temp=a[i]*3; if(temp>a[cn]) ans=min(ans,temp); temp=a[i]*5; if(temp>a[cn]) ans=min(ans,temp); temp=a[i]*7; if(temp>a[cn]) ans=min(ans,temp); } a[++cn]=ans; } int n; while(scanf("%d",&n),n){ int t=n%10; if(t==1 && n%100!=11){ printf("The %dst humble number is ",n); } else if(t==2 && n%100!=12){ printf("The %dnd humble number is ",n); } else if(t==3 && n%100!=13){ printf("The %drd humble number is ",n); } else{ printf("The %dth humble number is ",n); } printf("%I64d.\n",a[n]); } return 0;}
hdu 1058 Humble Numbers（构造？枚举？）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。