📰 来源: 博客园
原题链接：https://codeforces.com/gym/106495/problem/E
将 \(1 \sim N\)内的数，按其质因数分解序列的字典序进行排序，并回答\(Q\)次查询，每次求排在第\(K\) 位的数字是谁。
赛时队长大大灵机一动，突然受2025年省赛B题[https://qoj.ac/contest/2021/problem/10724]
暴力解法\(O(N\ logN)\)：跑两次for循环，用每个数的最小质因数标记该数
的思路启发，神来之手一发ac
/ 把队长ac代码小小优化过后，附上：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e6+5;
#define all(a) (a).begin()+1, (a).end()
void work(){
int n, q, k;
cin >> n >> q;
vector<int> a(n+1), p(n+1);
for(int i=2; i<=n; i++){ // 跑两次for循环，用每个数的最小质因数标记该数
for(int j=i; j<=n; j+=i){
if(!p[j]) p[j] = i;
}
}
for(int i=1; i<=n; i++) a[i] = i;
sort(all(a), [&](int x, int y){ // 迭代写法
while(p[x] == p[y]){ // 不断剔除相同的最小质因数，直到遇到不同的
if(p[x] == 0) return false;
x /= p[x];
y /= p[y];
}
return p[x] < p[y];
});
while(q--){
cin >> k;
cout << a[k] << '\n';
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while(T--) work();
}
/另附赛后补题的 常规解法：
核心思路：欧拉筛 + DFS
题目要求的质因数序列字典序，恰好完美契合深度优先搜索（DFS）的前序遍历顺序。
预处理素数（欧拉筛）：
使用欧拉筛预先求出 \(1 \sim N\) 范围内的所有素数，并从小到大保存在 prime 数组中。
构造搜索树（DFS）：
我们可以把数字看作是从 \(1\) 开始，不断乘以素数衍生出来的。
根节点：数字 \(1\)（对应空序列 \([]\)），首先将其加入答案数组。
分支：当前数字去乘以一个素数 \(p\)。为了保证质因数序列是非降序的（避免 \(2 \times 3\) 和 $3 \times 2$ 重复，且符合题目定义），每次 DFS 扩展时，只能乘以大于等于前一个质因数的素数（即代码中的 for (int i = idx; ...)）。
剪枝：如果 当前数字 * 质数 > N，说明越界了，直接 break 结束当前分支。
时间复杂度：预处理 \(O(N)\)（欧拉筛 \(O(N)\) + DFS遍历 \(1 \sim N\)每个数恰好一次\(O(N)\)）；查询 \(O(1)\)。总时间 \(O(N + Q)\)。
空间复杂度：\(O(N)\)，用于存储素数和最终的答案数组。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(a) (a).begin(), (a).end()
const int MAX = 1e6+5;
vector<int> prime, minp, maxp;
void euler(int n = MAX) {
minp.resize(n + 1);
maxp.resize(n + 1);
for (int i = 2; i <= n; i++) {
if (!minp[i]) {
minp[i] = maxp[i] = i;
prime.push_back(i);
}
for (auto j : prime) {
if (j > minp[i] || j > n / i) break;
minp[i * j] = j;
maxp[i * j] = maxp[i];
}
}
}
void solve(){
int n, q;
cin >> n >> q;
// for(int i=0; i<n; ++i){
// cout << prime[i] << " ";
// }
vector<ll> ans;
ans.push_back(1);
auto dfs = [&](auto &&self, ll sum, int idx) ->void {
for(int i=idx; i<prime.size(); ++i){
ll v = sum * prime[i];
if(v > n) break;
ans.push_back(v);
self(self, v, i);
}
};
dfs(dfs, 1, 0);
for(int i=0; i<q; ++i){
int x;
cin >> x;
cout << ans[x-1] << '\n';
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
euler();
int T = 1;
// cin >> T;
while(T--) solve();
}
/*
1
2
2*2
2*2*2
2*3
2*5
3
3*3
5
7
*/
🔗 原文链接: 点击阅读原文
文章评论