Save Princess(丑数)

Save Princess

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描述: Yesterday, the princess was kidnapped by a devil. The prince has to rescue our pretty princess.

"OK, if you want to save the beautiful princess, you must answer my questions correctly."the devil says.

"No problem!".

"I’ll ask you t questions. For each question, I’ll tell you an integer n, you must tell me the i th beatuiful number. If your answer is wrong, the princess and you will all die".

"But what is the characteristic of the beautiful number?" Pince asks.

"Beautiful numbers are numbers whose only prime factors are 2, 3 or 5. The sequence

1, 2, 3, 4, 5, 6, 8, 9, 10, ... shows the first 9 beautiful numbers.

By convention, 1 is included. "

Can you help the prince to save the princess?

输入

The input for each case is an integer n（1≤n≤5000) and it is terminated by a negative integer.

输出

For each test case, you should print an integer which represents the i th beautiful number.

样例输入

2
3
-1

样例输出

2
3

题解：这个方法解决丑数非常实用；

代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<vector> 
 7 #define mem(x,y) memset(x,y,sizeof(x))
 8 using namespace std;
 9 const int INF=0x3f3f3f3f;
10 const int MAXN=5010;
11 typedef long long LL;
12 LL ans[MAXN];
13 LL MIN(LL x,LL y,LL z){
14     LL d=x;
15     if(y<d)d=y;
16     if(z<d)d=z;
17     return d;
18 }
19 int main(){
20     int n,x_2=1,x_3=1,x_5=1;
21     LL d;
22     ans[1]=1;
23     int i=1;
24     while(i<=5000){
25         i++;
26         d=MIN(ans[x_2]*2,ans[x_3]*3,ans[x_5]*5);
27         ans[i]=d;
28         if(d==ans[x_2]*2)x_2++;
29         if(d==ans[x_3]*3)x_3++;
30         if(d==ans[x_5]*5)x_5++;
31     }
32     while(scanf("%d",&n),n>0)printf("%lld
",ans[n]);
33     return 0;
34 }