ls特别喜欢素数，他总是喜欢把素数集合的所有子集写下来，并按照一定的顺序和格式。对于每一个子集，集合内
的元素在写下来时是按照升序排序的，对于若干个集合，则以集合元素之和作为第一关键字，集合的字典序作为第
二关键字（先比较集合第一个元素，再比较第二个元素，以此类推），这个序列的开始如下：[2], [3], [2, 3],
[5], [2, 5], [7], [3, 5], [2, 7], [2, 3, 5], [3, 7], [11], [2, 3, 7], [5, 7], [2, 11], [13], [2, 5,
7]......注意：每个逗号的后面均有一个空格。现在ls想询问该序列位于区间[a,b]的子串是什么。
Input
输入仅一行包含两个数：a,b(1<=a<=b<=1e18,b-a<=100000)。
Output
输出序列中位于区间[a,b]的子串，前置或后置空格也应输出。
Sample Input
1 35
Sample Output
[2], [3], [2, 3], [5], [2, 5], [7],
题意：把素数集合按照和的大小排序，和相同的按照字典序排序，现在把这个排序后的序列看成一个字符串，问某个区间的字符串是什么。
思路：注意到素数不会太多，只有300来个，素数的和也不会太大，不会超过3000，所以我们递归去找即可。反正就是像数位DP那样搞就行了。。。
用记忆化递推缩小范围，然后用回溯暴力出ans。
#include<bits/stdc++.h> #define ll long long #define P pair<ll,ll> using namespace std; const int maxn=1e6; int isprime[maxn],p[maxn]; vector<int>primes; vector<int>vec; map<P,P>M; ll a,b,cur,prefix_len; int getL(int x){ int res=0; while(x>0){ res++; x/=10;} return res+2; } inline P get(P p1,P p2,ll len){ return P(p1.first+p2.first,p1.second+p2.second+len*p1.first); } P calc(int x,int sum) { P p(x,sum); if(sum<0) return P(0,0); if(M.count(p)) return M[p]; if(sum==0) return M[p]=P(1,2); //ct,len if(primes[x]>sum) return P(0,0); return M[p]=get(calc(x+1,sum-primes[x]),calc(x+1,sum),getL(primes[x])); } void ptchar(char c){ cur++; if(cur>=a&&cur<=b) putchar(c); } void print(int x){ vector<int>v; while(x>0){ v.push_back(x%10); x/=10;} for(int i=v.size()-1;i>=0;i--) ptchar(char(v[i]+'0')); } void print(int x,int sum) { if(sum<0||cur>=b) return ; if(sum==0){ ptchar('['); for(int i=0;i<vec.size();i++){ print(vec[i]); if(i==vec.size()-1) ptchar(']'); ptchar(','); ptchar(' '); } return ; } if(primes[x]>sum) return ; vec.push_back(primes[x]); prefix_len+=getL(primes[x]); ll len=prefix_len*calc(x+1,sum-primes[x]).first+calc(x+1,sum-primes[x]).second; if(len+cur>=a) print(x+1,sum-primes[x]); else cur+=len; vec.pop_back(); prefix_len-=getL(primes[x]); len=prefix_len*calc(x+1,sum).first+calc(x+1,sum).second; if(len+cur>=a) print(x+1,sum); else cur+=len; } int main() { freopen("list.in","r",stdin); freopen("list.out","w",stdout); isprime[1]=false; fill(isprime,isprime+maxn,true); for(int i=2;i<maxn;i++){ if(isprime[i]){ primes.push_back(i); for(int j=i+i;j<maxn;j+=i) isprime[j]=false; } } scanf("%I64d%I64d",&a,&b); for(int i=2;i<100000&&cur<b;i++){ //试探过，i最大到2096，这个范围的素数也就300来个，所以记忆化 ll len=calc(0,i).second; if(cur+len>=a) print(0,i); else cur+=len; } puts(""); return 0; }