有一个整数序列，序列中每个元素的质因数只有 2 , 3 , 5 2,3,5，该序列的前几个元素为 1 , 2 , 3 , 4 , 5 , 6 , 8 , 9 , 10 … 1,2,3,4,5,6,8,9,10…。按惯例，1也作为序列中的元素，且是序列中的第一个元素。现在感兴趣的是，给定一个位置 � ( 1 ≤ � ≤ 10000 ) n(1≤n≤10000)，该序列中第 � n个元素是多少？ 输入 输入有若干行，每行为一个整数 � n，为查询的元素位置。 输出 对每行输入，在单独的行中输出序列中对应位置的元素。

这是一个经典的题目，可以使用动态规划来解决。具体来说，我们可以维护三个指针，分别指向下一个将 2 乘上去的数、下一个将 3 乘上去的数和下一个将 5 乘上去的数。每次取这三个数中的最小值作为新的数，并将对应的指针向前移动一步。这样得到的序列就是符合要求的序列。

下面是使用 Python 语言实现的代码：

n = int(input())
dp = [1] * n
p2, p3, p5 = 0, 0, 0
for i in range(1, n):
    dp[i] = min(dp[p2]*2, dp[p3]*3, dp[p5]*5)
    if dp[i] == dp[p2]*2:
        p2 += 1
    if dp[i] == dp[p3]*3:
        p3 += 1
    if dp[i] == dp[p5]*5:
        p5 += 1
for i in range(n):
    print(dp[i])

注意，这里的序列下标从 0 开始。如果需要输出第 k 个元素，只需要输出 dp[k-1]。

相关问题

有一个整数序列，序列中每个元素的质因数只有2，3，5

这个问题描述了一个数列，该数列中每个元素的质因数只有2、3、5，数列前几个元素为2、3、52、3、5，问该数列前几个元素中有多少个是1、2、3、4、5、6、8、9、10……（1、2、3、4、5、6、8、9、10……表示正整数序列）

举个例子，1也是该数列中的元素，而第一个元素是该数列中的第一个元素。现在要求指定一个位置n（1≤n≤10000），问该数列中第n个元素的质因数有多少个？

有一个整数序列，序列中每个元素的质因数只有2,3,52,3,5，该序列的前几个元素为1,2,3,4,5,6,8,9,10\dots1,2,3,4,5,6,8,9,10…。按惯例，1也作为序列中的元素，且是序列中的第一个元素。现在感兴趣的是，给定一个位置n(1 \le n \le 10000)n(1≤n≤10000)，该序列中第nn个元素是多少？

这个问题描述了一个数列，该数列中每个元素的质因数只有2、3、5，数列前几个元素为2、3、52、3、5，问该数列前几个元素中有多少个是1、2、3、4、5、6、8、9、10……（1、2、3、4、5、6、8、9、10……表示正整数序列）

举个例子，1也是该数列中的元素，而第一个元素是该数列中的第一个元素。现在要求指定一个位置n（1≤n≤10000），问该数列中第n个元素的质因数有多少个？