1067: Humble Number

题目描述

如果一个数只有素数因子2，3，5，7，那么这个数被称为“Humble Number”。前20个“Humble Number”是：1，2，3，4，5，6，7，8，9，10，12，14，15，16，18，20，21，24，25，27。经验证，2000000000以内的“Humble Number”共有5842个。
你的任务是编写一个程序，根据要求输出序列中的某一个数。

如 22, 不能拆解为2a+3b+5c+7d=22, 因此22不是“Humble Number”

输入

输入数据是一列整数，每行一个，表示要求输出的数再“Humble Number”序列中的序数，输入的结束是一个数字0，这个数字不作处理。

输出

对于每一个输入的数字，输出“Humble Number”数列中相应位置的数字，每个数字占一行。

样例输入

1
2
3
4
11
12
13
21
22
23
100
1000
5842
0

样例输出

1
2
3
4
12
14
15
28
30
32
450
385875
2000000000

思路

最容易想到就是枚举法, 从1开始, 判断每一个数是否为“Humble Number”, 是的话存入数组中. 这样做会有一个问题, 就是越往后, 无效的运算越多. 当数字较大时, “Humble Number”的分布是十分稀疏的.

将问题转化为, 直接生成“Humble Number”, 计算量会少很多.“Humble Number”可以分解为另一个“Humble Number”乘以基数"2,3,5,7"之一. 因此可以从最小的“Humble Number” 1 开始推.

• 设一个基数数组 factors[4] =

• 设一个Humble Number数组 num[5842] = {0}, num[0] = 1;

• 维护一个位置数组pos[4] =

• 计算公式 Humble Number (n) = min

  • min{ Humble Number (pos[i])*factors[i] }, 既保证了Humble Number数组从小到大排序, 又保证了不会出现重复的结果

• 每算出一个新的Humble Number, 计算这个Humble Number时, min{ Humble Number (pos[i])*factors[i] } 中对应的pos后移一位

  • 如 pos = {0,0,0,0} 时, min{ Humble Number (pos[i])*factors[i] } = 2, 此时i=0, 就让pos[0] ++

代码

#include<stdio.h>
#define MAX_NUM 20000000
#define TABLE_LEN 5842

int main(void){
    int factors[4] = {2,3,5,7};
    int pos[4] = {0,0,0,0};
    int table[TABLE_LEN];
    table[0] = 1;
    int i;
    for(i = 1; i < TABLE_LEN; i++){
        int j = 0;
        int num[4] = {
            factors[0]*table[pos[0]],
            factors[1]*table[pos[1]],
            factors[2]*table[pos[2]],
            factors[3]*table[pos[3]]
        };
        int min = 0;
        min = num[min]<num[1]?min:1;
        min = num[min]<num[2]?min:2;
        min = num[min]<num[3]?min:3;
        if(table[i-1]!=num[min]){
            table[i] = num[min];
        }else{
            i--;
        }
        pos[min]++;
    }
    while(1){
        scanf("%d",&i);
        if(!i) break;
        printf("%d\n",table[i-1]);
    }    
    return 0;
}

补充

判断一个数是否为“Humble Number”

• 将这个数除以2, 直到无法整除
• 继续除以3, 直到无法整除
• 继续除以5, 直到无法整除
• 继续除以7, 直到无法整除

上述四步中, 若有一步出现完全整除, 则为“Humble Number”