hdu 1085 Humble Numbers（打表）

2018年01月12日 ⁄ 综合 ⁄ 共 2105字 ⁄ 字号 评论关闭

HumbleNumber[i]是比Humblenumber[i-1][0]大的一个数，从HumbleNumber[1~i][1~4]都搜一遍 找出来了，复杂度O（N^2）

#include<iostream>
#include<cstdio>
using namespace std;
long long BumbleNumber[6000][5];
int prime[5]={0,2,3,5,7};
int main()
{
int N;
for(int i=1;i<=10;i++)
BumbleNumber[i][0]=i;
for(int i=1;i<=10;i++)
for(int j=1;j<=4;j++)
BumbleNumber[i][j]=BumbleNumber[i][0]*prime[j];

for(int i=11;i<=5842;i++)
{
int temp=BumbleNumber[i-1][0],ans=2000000001;
for(int j=1;j<=i-1;j++)
{
for(int k=1;k<=4;k++)
if(BumbleNumber[j][k]>temp && BumbleNumber[j][k]<ans)
ans=BumbleNumber[j][k];
}
BumbleNumber[i][0]=ans;
for(int k=1;k<=4;k++)
{
if(BumbleNumber[i][0]*prime[k]>2000000001)
BumbleNumber[i][k]=2000000001;
else
BumbleNumber[i][k]=BumbleNumber[i][0]*prime[k];
}
}
while(cin>>N)
{
if(N==0)
{ break; }
if(N%10==1&&N%100!=11)
{
cout<<"The "<<N<<"st humble number is "<<BumbleNumber[N][0]<<"."<<endl;
continue;
}
if(N%10==2&&N%100!=12)
{
cout<<"The "<<N<<"nd humble number is "<<BumbleNumber[N][0]<<"."<<endl;
continue;
}
if(N%10==3&&N%100!=13)
{
cout<<"The "<<N<<"rd humble number is "<<BumbleNumber[N][0]<<"."<<endl;
continue;
}
cout<<"The "<<N<<"th humble number is "<<BumbleNumber[N][0]<<"."<<endl;
}
}

#include <iostream>
#include <cstring>
using namespace std;
int min(int a,int b){
if(a<b) return a;
else return b;
}
int main(void){
long D[5843];
memset(D,0,sizeof(D));
D[1]=1;
int i,i1=1,i2=1,i3=1,i4=1;
int t1,t2,t3,t4;
for(i=2;i<5843;i++){
t1=D[i1]*2;
t2=D[i2]*3;
t3=D[i3]*5;
t4=D[i4]*7;
D[i]=min(min(t1,t2),min(t3,t4));
if(D[i]==t1) i1++;
if(D[i]==t2) i2++;
if(D[i]==t3) i3++;
if(D[i]==t4) i4++;
}
int n;
cin>>n;
while(n){
if(n%10==1&&n%100!=11){
cout<<"The "<<n<<"st humble number is "<<D[n]<<"."<<endl;
}
else if(n%10==2&&n%100!=12){
cout<<"The "<<n<<"nd humble number is "<<D[n]<<"."<<endl;
}
else if(n%10==3&&n%100!=13){
cout<<"The "<<n<<"rd humble number is "<<D[n]<<"."<<endl;
}else{
cout<<"The "<<n<<"th humble number is "<<D[n]<<"."<<endl;
}
cin>>n;
}
system("pause");
return 0;
}