Humble Numbers 丑数

2024-08-28 07:48

文章标签 numbers 丑数 humble

本文主要是介绍Humble Numbers 丑数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1058

很多人都说这道题是水题，但对于我来说还是很有用的，它教会我在处理这种问题的时候为了节省时间我们可以先把所有的满足范围的丑数找出来，再进行下面的操作。和去年吉林省省赛那道素数题相似。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>

#define maxn 10000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657

const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b){
    return a>b;
}
int a[6000];
void init()
{
    int n1=1,n2=1,n3=1,n4=1;
    int k=1;a[1]=1;
    while(k<=5842)
    {
        k++;
        a[k]=min(a[n1]*2,min(a[n2]*3,min(a[n3]*5,a[n4]*7)));
        if(a[k]==a[n1]*2)n1++;
        if(a[k]==a[n2]*3)n2++;
        if(a[k]==a[n3]*5)n3++;
        if(a[k]==a[n4]*7)n4++;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    init();
    int n;
    while(cin>>n&&n)
    {
        if(n==0)break;
        if(n%10==1&&n%100!=11)cout<<"The "<<n<<"st humble number is "<<a[n]<<"."<<endl;
        else if(n%10==2&&n%100!=12)cout<<"The "<<n<<"nd humble number is "<<a[n]<<"."<<endl;
        else if(n%10==3&&n%100!=13)cout<<"The "<<n<<"rd humble number is "<<a[n]<<"."<<endl;
        else cout<<"The "<<n<<"th humble number is "<<a[n]<<"."<<endl;

    }
    return 0;
}