UVa 11669 Non Decreasing Prime Sequence

题目描述

非递减素数序列（NDPS\texttt{NDPS}NDPS）是一个由素数组成的序列，满足第iii个元素不小于第i−1i - 1i−1个元素（i>1i > 1i>1）。一个NDPS\texttt{NDPS}NDPS的权重定义为该序列所有元素的乘积。

定义序列aaa小于序列bbb，若aaa的元素个数小于bbb的元素个数；若元素个数相同，则按字典序比较。给定区间[A,B][A, B][A,B]（A≤BA \le BA≤B），需要找出所有权重在[A,B][A, B][A,B]范围内的NDPS\texttt{NDPS}NDPS中第KKK小的序列。

输入格式

第一行包含整数TTT（T≤5000T \le 5000T≤5000），表示测试用例数量。接下来TTT行，每行三个整数AAA、BBB和KKK（2≤A≤B≤10000002 \le A \le B \le 10000002≤A≤B≤1000000）。保证至少存在KKK个符合条件的NDPS\texttt{NDPS}NDPS。

输出格式

对于每个测试用例，输出一行，格式为Case x:，后接该用例的第KKK小NDPS\texttt{NDPS}NDPS序列，元素之间用空格分隔。

样例输入

3 2 10 1 2 10 5 2 10 9

样例输出

Case 1: 2 Case 2: 2 2 Case 3: 2 2 2

题目分析

问题核心在于：给定数值区间[A,B][A, B][A,B]，需要枚举所有权重在该区间内的非递减素数序列，并按照特定规则排序（长度优先，字典序次之），然后输出第KKK个。

直接枚举所有可能的素数序列不可行，因为组合数量庞大。观察到序列的权重等于各素数的乘积，且序列是非递减的，这本质上对应着一个整数的质因数分解。任意一个正整数NNN，将其质因数按非递减顺序排列，恰好构成一个唯一的NDPS\texttt{NDPS}NDPS，其乘积为NNN。例如N=12=2×2×3N = 12 = 2 \times 2 \times 3N=12=2×2×3，对应的NDPS\texttt{NDPS}NDPS就是[2, 2, 3]。

因此，题目转化为：在区间[A,B][A, B][A,B]内的所有整数中，对其质因数分解结果（按非递减顺序排列的质因数序列）进行排序，排序规则为先比较序列长度（即质因数个数，含重数），长度相同则比较字典序，然后输出第KKK个序列。

这样，问题规模被压缩到B≤106B \le 10^6B≤106，可枚举范围内的所有整数并预处理其质因数分解结果。

解题思路

预处理质因数分解

首先使用线性筛法求出111到10610^6106内每个数的最小质因子（spf\texttt{spf}spf）。然后利用spf\texttt{spf}spf对每个数进行质因数分解，将分解出的质数按非递减顺序存入factors[x]数组。由于分解过程本身保证了质因数按从小到大的顺序出现，因此factors[x]天然就是一个非递减素数序列，且其乘积恰好为xxx。

排序规则与序列生成

需要按照题目定义的顺序对所有x∈[2,106]x \in [2, 10^6]x∈[2,106]对应的序列进行全局排序。排序规则为：

1. 序列长度（即质因数个数）较小者更小。
2. 若长度相同，则按字典序比较序列。

因此，可构造一个包含所有整数222到10610^6106的数组order，并使用自定义比较函数进行排序：先比较factors[a].size()，再比较factors[a]与factors[b]的字典序。

区间查询优化

由于T≤5000T \le 5000T≤5000，若对每个测试用例都扫描整个order数组，时间复杂度为O(T⋅N)O(T \cdot N)O(T⋅N)，其中N=106−1N = 10^6 - 1N=106−1，可能超时。因此采用分块思想优化区间查询。

将排序后的order数组分成若干块，每块大小为blockSize\texttt{blockSize}blockSize（取250025002500）。对每个块，将其中的元素按数值大小排序（升序），以便快速统计块内有多少个权重在[A,B][A, B][A,B]之间。

对于每个查询(A,B,K)(A, B, K)(A,B,K)，遍历所有块：

• 在块内使用lower_bound和upper_bound统计数值落在[A,B][A, B][A,B]内的元素个数。
• 若累计个数达到KKK，则在该块内部顺序扫描原始order块内的元素，找到第KKK个满足权重条件的元素，即为答案。

这种方法将单次查询的复杂度降至O(块数⋅log⁡块大小+块大小)O(\text{块数} \cdot \log \text{块大小} + \text{块大小})O(块数⋅log块大小+块大小)，在给定数据范围内表现良好。

正确性说明

• 质因数分解的唯一性保证了每个NDPS\texttt{NDPS}NDPS与一个整数一一对应。
• 全局排序的order数组严格按照题目定义的序列顺序排列，因此区间查询时只需按该顺序选择第KKK个满足权重条件的元素。
• 分块查询准确统计了区间内的元素个数，并确保输出的是全局第KKK小的序列。

复杂度分析

• 预处理线性筛：O(V)O(V)O(V)，其中V=106V = 10^6V=106。
• 质因数分解：O(Vlog⁡V)O(V \log V)O(VlogV)。
• 全局排序：O(Vlog⁡V⋅L)O(V \log V \cdot L)O(VlogV⋅L)，其中LLL为分解结果的平均长度，但比较操作在vector\texttt{vector}vector上开销较小。
• 查询：O(T⋅(VblockSize⋅log⁡blockSize+blockSize))O(T \cdot (\frac{V}{\text{blockSize}} \cdot \log \text{blockSize} + \text{blockSize}))O(T⋅(blockSizeV​⋅logblockSize+blockSize))。
• 空间复杂度：O(V⋅L)O(V \cdot L)O(V⋅L)存储所有质因数分解结果。

代码实现

// Non Decreasing Prime Sequence// UVa ID: 11669// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.730s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXV=1000000;vector<int>spf(MAXV+1);vector<vector<int>>factors(MAXV+1);voidprecompute(){vector<int>primes;for(inti=2;i<=MAXV;++i){if(!spf[i]){spf[i]=i;primes.push_back(i);}for(intp:primes){if(p>spf[i]||1LL*i*p>MAXV)break;spf[i*p]=p;}}for(inti=2;i<=MAXV;++i){intx=i;while(x>1){intp=spf[x];while(x%p==0){factors[i].push_back(p);x/=p;}}}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);precompute();vector<int>order;order.reserve(MAXV-1);for(inti=2;i<=MAXV;++i)order.push_back(i);sort(order.begin(),order.end(),[&](inta,intb){if(factors[a].size()!=factors[b].size())returnfactors[a].size()<factors[b].size();returnfactors[a]<factors[b];});intN=(int)order.size();intblockSize=2500;intnumBlocks=(N+blockSize-1)/blockSize;vector<int>blockStart(numBlocks),blockEnd(numBlocks);vector<vector<int>>blockSorted(numBlocks);for(intb=0;b<numBlocks;++b){intl=b*blockSize;intr=min(N,l+blockSize);blockStart[b]=l;blockEnd[b]=r;blockSorted[b].reserve(r-l);for(inti=l;i<r;++i)blockSorted[b].push_back(order[i]);sort(blockSorted[b].begin(),blockSorted[b].end());}intT;cin>>T;for(inttc=1;tc<=T;++tc){intA,B,K;cin>>A>>B>>K;intans=-1;intcnt=0;for(intb=0;b<numBlocks;++b){auto&vec=blockSorted[b];autoitL=lower_bound(vec.begin(),vec.end(),A);autoitR=upper_bound(vec.begin(),vec.end(),B);intnum=(int)(itR-itL);if(cnt+num>=K){intneed=K-cnt;for(inti=blockStart[b];i<blockEnd[b];++i){intw=order[i];if(w>=A&&w<=B){--need;if(need==0){ans=w;break;}}}break;}elsecnt+=num;}cout<<"Case "<<tc<<": ";constauto&fac=factors[ans];for(size_t i=0;i<fac.size();++i){if(i)cout<<' ';cout<<fac[i];}cout<<'\n';}return0;}

总结

本题巧妙地将非递减素数序列问题转化为整数的质因数分解排序问题，利用了算术基本定理中的唯一分解性。主要技巧包括：

• 模型转换：将序列问题转化为整数及其质因数分解，极大简化了问题结构。
• 预处理与排序：通过一次性预处理所有可能的序列并排序，使得多次查询能够快速响应。
• 分块优化：在区间查询中引入分块，平衡了时间与空间，避免了O(T⋅N)O(T \cdot N)O(T⋅N)的线性扫描。

该方法的核心在于将组合生成问题转化为静态数据上的查询问题，适用于BBB较小（10610^6106）且查询次数较多的场景。掌握这种转化思想，对处理类似的大规模枚举与排序问题具有重要参考价值。