本文共 1837 字，大约阅读时间需要 6 分钟。
在数论领域，某些数的生成方式可以通过质因数的乘积来解释。特别是，所有符合条件的数都可以表示为2、3、5、7的乘积。这样一个数列的生成规则可以通过以下方式来理解：
下一个数的生成规则基于质因数的乘积特性。每个数都是前一个数与2、3、5、7中的一个质因数相乘得到的。为了找到下一个数，我们需要确定最小的乘积方式。
为了实现这一点，我们可以使用一种称为“最小堆”的数据结构。通过这种方法，我们可以高效地生成每个数列中的下一个数。具体来说，我们将数列分为四个独立的序列，每个序列对应一个质因数（2、3、5、7）。这样做的好处是每个序列都可以独立地生成下一个数，而不会干扰其他序列的生成。
为了实现上述生成规则，我们可以使用以下步骤：
初始化：我们需要预先定义四个数组，分别用于跟踪每个序列的当前位置（p2、p3、p5、p7）。
生成下一个数：对于每个数n，我们计算四个可能的下一个数（分别是n2、n3、n5、n7）。然后，我们选择最小的这两个数中的较大者作为n+1的值。
更新指针：根据生成的n+1的值，我们更新对应的序列指针（p2、p3、p5、p7）。这样，每个序列都能按照自己的规律独立地生成数列。
重复上述过程：直到我们处理完所有的数为止。
这种方法的核心在于通过预先定义的数组和指针，我们可以轻松地跟踪每个序列的生成情况，从而保证数列的正确性和高效性。
#include#define MAXN (1e18)#define Maxn 80000long long n, ans[Maxn + 1];long long p2, p3, p5, p7;long long f2[Maxn], f3[Maxn], f5[Maxn], f7[Maxn];long long all, a, b;int main() { all = 1; ans[1] = 1; p2 = p3 = p5 = p7 = 1; for (int i = 1; i < Maxn; i++) { f2[i] = ans[i] * 2; f3[i] = ans[i] * 3; f5[i] = ans[i] * 5; f7[i] = ans[i] * 7; a = (f2[p2] < f3[p3] ? f3[p3] : f2[p2]); b = (f5[p5] > f7[p7] ? f7[p7] : f5[p5]); ans[i + 1] = (a > b) ? b : a; if (ans[i + 1] == f2[p2]) { p2++; } if (ans[i + 1] == f3[p3]) { p3++; } if (ans[i + 1] == f5[p5]) { p5++; } if (ans[i + 1] == f7[p7]) { p7++; } } int t; scanf("%d", &t); while (t--) { scanf("%lld", &n); printf("%lld\n", ans[n]); } return 0;}
定义变量：我们定义了一个很大的数组ans，用于存储数列中的每一个数。另外，我们还定义了四个指针p2、p3、p5、p7，用于跟踪每个序列的当前位置。
初始化：初始时，所有序列的当前位置都被设置为1，表示初始数为1。
生成序列：对于每一个数i，我们计算四个可能的下一个数（分别乘以2、3、5、7）。然后，我们选择这四个数中的最大值作为ans[i+1]的值。
更新指针：根据生成的ans[i+1]的值，我们更新对应的序列指针，使得每个序列都能按照自己的规律独立地生成数列。
输入处理：最后，我们处理输入的查询，输出对应的数列值。
这种方法通过预先定义的数组和指针，确保了数列的高效生成和正确性。无论是从性能还是从正确性上来看，这种方法都表现得非常出色。
转载地址：http://ucxfk.baihongyu.com/