首页 > 其他 > 详细

HDU 1058 Humble Numbers (dp+打表)

时间:2014-08-18 18:32:52      阅读:362      评论:0      收藏:0      [点我收藏+]


先是想筛法素数表啊,然后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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!