自然数集合 比赛题目 题目统计 全部提交 时间限制:C/C++ 1000MS,其他语言 2000MS 内存限制:C/C++ 256MB,其他语言 512MB 分数:98 描述 大数学家高斯小时候偶然间发现一种有趣的自然数集合 Blash ,对应以 a 为基的集合 Ba 定义如下: (1)a 是集合 Ba 的基,且 a 是 Ba 的第一个元素。 (2)如果 x 在集合 Ba 中,则 2x+1 和 3x+1 也都在集合 Ba 中。 (3)没有其他元素在集合 Ba 中了。 现在小高斯想知道如果将集合Ba中元素按照升序排列起来是什么样? 输入描述 输入一行包括两个数字,集合的基a(1<=a<=50)以及所求元素序号n(1<=n<=1000000)。 输出描述 按照从小到大的顺序输出集合的前n个,每个数字之间用一个空格分开
时间: 2024-03-31 13:33:56 浏览: 12
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void generateSet(vector<long long>& s, long long a, int n) {
s.push_back(a);
if (s.size() == n) {
return;
}
generateSet(s, 2 * a + 1, n);
generateSet(s, 3 * a + 1, n);
}
int main() {
long long a;
int n;
cin >> a >> n;
vector<long long> s;
generateSet(s, a, n);
sort(s.begin(), s.end());
for (int i = 0; i < n; i++) {
cout << s[i] << " ";
}
cout << endl;
return 0;
}
```
注意,这个算法时间复杂度比较高,为O(2^n),因为每个元素会生成两个新的元素,所以集合大小会呈指数级增长。在实际应用中需要注意性能问题。