MoBrook | 溪月阁

Description

“丑数”是指除了质因子2,3，5，不含其它质因子的正整数，例如由小到大前10个“丑数”为
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
现要求编写一个程序，输出指定第几位的“丑数”。

输入格式

第一行为正整数T（T<=10000）, 表示case的数目。
此后T行，每行一个正整数 n (n <= 100000000).

输出格式

每一个n，输出第n个“丑数”

输入样例

3
1
2
9

输出样例

1
2
10

作者 admin

#include<iostream>
using namespace std;
int Min(int a,int b,int c)
{
    int d=a<b?a:b;
    return c<d?c:d;
}
int main()
{
    int T;cin>>T;
    while(T--)
    {
        int n;cin>>n;
        int i;
        int u[n];
        u[1]=1;
        int index_2=1,index_3=1,index_5=1;
        for(i=2;i<=n;i++)
        {
            int c=Min(2*u[index_2],3*u[index_3],5*u[index_5]);
            u[i]=c;
            if(c==2*u[index_2])index_2++;
            if(c==3*u[index_3])index_3++;
            if(c==5*u[index_5])index_5++;
        }
        cout<<u[n]<<endl;
    }
}

Mark

已知1、2、3、5为丑数，且任意丑数相乘都是丑数，以此规则生成丑数序列。

2*1 == 2    3*1 == 3    5*1 == 5  取最小值2为新的丑数，即第二个丑数为2，则2已经乘过第一个丑数1，下次2就只能乘第二个丑数2
 2*2 == 4    3*1 == 3    5*1 == 5  取最小值3为新的丑数，即第三个丑数为3，则3已经乘过第一个丑数1，下次3就只能乘第二个丑数2
 2*2 == 4    3*2 == 6    5*1 == 5  取最小值4为新的丑数，即第四个丑数为4，则2已经乘过第二个丑数2，下次2就只能乘第三个丑数3
 2*3 == 6    3*2 == 6    5*1 == 5  取最小值5为新的丑数，即第五个丑数为5，则5已经乘过第一个丑数1，下次5就只能乘第二个丑数2
 2*3 == 6    3*2 == 6    5*2 == 10 取最小值6为新的丑数，即第六个丑数为6，则认为2已经乘过第三个丑数3，3已经乘过第二个丑数2
————————————————
版权声明：此段解释摘取自CSDN博主「Hunter_Kevin」的原创文章。
原文链接：https://blog.csdn.net/Hunter_Kevin/article/details/117536167