hdu 1058 Humble Numbers（dp/暴力)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;

#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
//#define CLR(a) memset(a,0,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
const double eps=1e-6;
const int INF = 0x3f3f3f3f;
int n;
ll p2[10010],p3[10010],p5[10010],p7[10010];
ll base=2000000000;
vector<ll>v;
int main(){
    ll num=1;
    p2[0]=1;
    int cnt=0;
    while(p2[cnt]<base){
        p2[cnt+1]=(ll)(2*p2[cnt]);
        ++cnt;
    }

    num=1;
    p3[0]=1;
    cnt=0;
    while(p3[cnt]<base){
        p3[cnt+1]=(ll)(3*p3[cnt]);
        ++cnt;
    }
    num=1;
    p5[0]=1;
    cnt=0;
    while(p5[cnt]<base){
        p5[cnt+1]=(ll)(5*p5[cnt]);
        ++cnt;
    }
    num=1;
    p7[0]=1;
    cnt=0;
    while(p7[cnt]<base){
        p7[cnt+1]=(ll)(7*p7[cnt]);
        ++cnt;
    }

    v.push_back(0);

    rep(i,0,100){
        ll sum = p2[i];
        if(sum>base)break;
        rep(j,0,100){
            ll sum1 = sum*p3[j];
            if(sum1>base)break;
            rep(k,0,100){
                ll sum2 = sum1*p5[k];
                if(sum2>base)break;
                rep(p,0,100){
                    ll sum3 = sum2*p7[p];
                    if(sum3>base)break;
                    v.push_back(sum3);
                }
            }
        }
    }
    sort(v.begin(),v.end());
    while(scanf("%d", &n)!=EOF&&n){
        if(n%10==1&&n%100!=11){
            printf("The %dst humble number is %I64d.\n", n,v[n]);
        }else if(n%10==2&&n%100!=12){
            printf("The %dnd humble number is %I64d.\n", n,v[n]);
        }else if(n%10==3&&n%100!=13){
            printf("The %drd humble number is %I64d.\n", n,v[n]);
        }else{
            printf("The %dth humble number is %I64d.\n", n,v[n]);
        }
    }
    return 0;
}

#include <iostream>
#include <cstdio>
 
using namespace std;
 
const int maxn = 5843;
int humber[maxn];
 
void prepare() {
	int i;
	humber[1] = 1;
	int na;
	int nb;
	int nc;
	int nd;
	int pos1 = 1;
	int pos2 = 1;
	int pos3 = 1;
	int pos4 = 1;
 
	for (i = 2; i <= maxn; ++i) {
		//从符合要求的数中找到最小的那个数作为目前humber数
		humber[i] = min(min(na = humber[pos1] * 2,nb = humber[pos2] * 3),
						min(nc = humber[pos3] * 5, nd = humber[pos4] * 7));
 
		if (humber[i] == na) {//如果选择了这个因子,则将起索引向后移一位
			pos1++;
		}
		if (humber[i] == nb) {
			pos2++;
		}
		if (humber[i] == nc) {
			pos3++;
		}
		if(humber[i] == nd){
			pos4++;
		}
 
	}
}
 
int main() {
	prepare();
	int n;
	while (scanf("%d", &n) != EOF, n) {
		 printf("The %d",n);
 
		if (n % 100 != 11 && n % 10 == 1){
			printf("st");
		}else if (n % 100 != 12 && n % 10 == 2){
			printf("nd");
		}else if (n % 100 != 13 && n % 10 == 3){
			printf("rd");
		}else{
			printf("th");
		}
		printf(" humble number is %d.\n",humber[n]);
	}
 
	return 0;
}