51nod 1010 只包含因子2 3 5的数

51nod 1010 只包含因子2 3 5的数

K的因子中只包含2 3 5。
满足条件的前10个数是：2,3,4,5,6,8,9,10,12,15。
所有这样的K组成了一个序列S，现在给出一个数n，求S中 >= 给定数的最小的数。
例如：n = 13，S中 >= 13的最小的数是15，所以输出15。
输入
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行1个数N(1 <= N <= 10^18)
输出
共T行，每行1个数，输出>= n的最小的只包含因子2 3 5的数。
输入样例
5
1
8
13
35
77
输出样例
2
8
15
36
80

思路一：
外置函数，判断是否只含因数2/3/5。
超时。————因为(1 <= N <= 10^18)
思路二：
空间换时间，做表，打出S。

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    long long a[100001] = {0};
    int k, x, y, z;
    x = y = z = 0;
    a[0] = 1;
    for (int i = 1; i <= 100000; i++) {
        a[i] = min(2 * a[x], min(3 * a[y], 5 * a[z]));
        if (a[i] == 2 * a[x]) x++;
        if (a[i] == 3 * a[y]) y++;
        if (a[i] == 5 * a[z]) z++;
    }


a[0]=2;
long long m,n;
cin>>n;
while(n--){
cin>>m;
for (k = 0;; k++)
if (a[k] >= m) break;
cout << a[k] << endl;

}
}

** 做表重点代码！！！**

for (int i = 1; i <= 100000; i++) {
a[i] = min(2 * a[x], min(3 * a[y], 5 * a[z]));
if (a[i] == 2 * a[x]) x++;
if (a[i] == 3 * a[y]) y++;
if (a[i] == 5 * a[z]) z++;
}

天道酬勤。