先是想筛法素数表啊,然后1~2000000000枚举打表啊,结果越想越不对。
后来想到唯一分解定理,可是怎么实现呢。。果然还是需要努力啊。。
研究了discuss代码,码之~
~~~~
dp的思想,若dp[i]是Humble Numbers,那么dp[i]*2,dp[i]*3,dp[i]*5,dp[i]*7都将是Humble Numbers。
所以只需要注意连续性便好了。
#include<cstdio> #include<algorithm> #include<cmath> #define LL __int64 #define N 6000 using namespace std; LL f[N]={0,1}; void dp() { int x,y,p,q; x=y=p=q=1; for(int i=2;i<=5842;i++) { //取最小值以保持连续性 f[i]=min(f[x]*2,min(f[y]*3,min(f[p]*5,f[q]*7))); if(f[i]==f[x]*2) x++; //取下一个作为因子 if(f[i]==f[y]*3) y++; if(f[i]==f[p]*5) p++; if(f[i]==f[q]*7) q++; } } int main() { dp(); int n; while(~scanf("%d",&n),n) { //输出注意11,12,13,113,···的情况。 if(n%10==1 && n%100!=11) printf("The %dst humble number is %I64d.\n",n,f[n]); else if(n%10==2 && n%100!=12) printf("The %dnd humble number is %I64d.\n",n,f[n]); else if(n%10==3 && n%100!=13) printf("The %drd humble number is %I64d.\n",n,f[n]); else printf("The %dth humble number is %I64d.\n",n,f[n]); } return 0; }
看到个漂亮的暴力代码。如下~
#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; const int maxn = 2000000000; int main() { __int64 i, j, k, r, g = 1, a[6000]; for(i=0; i<31 && pow(2,i)<=maxn; i++) for(j=0; j<20 && pow(2,i)*pow(3,j)<=maxn; j++) for(k=0; k<14 && pow(2,i)*pow(3,j)*pow(5,k)<=maxn; k++) for(r=0; r<12 && pow(2,i)*pow(3,j)*pow(5,k)*pow(7,r)<=maxn; r++) a[g++] = pow(2,i)*pow(3,j)*pow(5,k)*pow(7,r); sort(a+1,a+g+1); int t; while(~scanf("%d", &t), t) { printf("The %d", t); if(t%10 == 1 && t%100 != 11) printf("st "); else if(t%10 == 2 && t%100 != 12) printf("nd "); else if(t%10 == 3 && t%100 != 13) printf("rd "); else printf("th "); printf("humble number is %d.\n", a[t]); } return 0; }
HDU 1058 Humble Numbers (dp+打表),布布扣,bubuko.com
HDU 1058 Humble Numbers (dp+打表)
原文:http://blog.csdn.net/darwin_/article/details/38663031