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=;
while(x>){ res++; x/=;}
return res+;
}
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<) return P(,);
if(M.count(p)) return M[p];
if(sum==) return M[p]=P(,); //ct,len
if(primes[x]>sum) return P(,);
return M[p]=get(calc(x+,sum-primes[x]),calc(x+,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>){ v.push_back(x%); x/=;}
for(int i=v.size()-;i>=;i--) ptchar(char(v[i]+''));
}
void print(int x,int sum)
{
if(sum<||cur>=b) return ;
if(sum==){
ptchar('[');
for(int i=;i<vec.size();i++){
print(vec[i]);
if(i==vec.size()-) 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+,sum-primes[x]).first+calc(x+,sum-primes[x]).second;
if(len+cur>=a) print(x+,sum-primes[x]);
else cur+=len; vec.pop_back();
prefix_len-=getL(primes[x]);
len=prefix_len*calc(x+,sum).first+calc(x+,sum).second;
if(len+cur>=a) print(x+,sum);
else cur+=len;
}
int main()
{
freopen("list.in","r",stdin);
freopen("list.out","w",stdout);
isprime[]=false;
fill(isprime,isprime+maxn,true);
for(int i=;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=;i<&&cur<b;i++){ //试探过,i最大到2096,这个范围的素数也就300来个,所以记忆化
ll len=calc(,i).second;
if(cur+len>=a) print(,i);
else cur+=len;
}
puts("");
return ;
}

最新文章

  1. 20145216 20145330 《信息安全系统设计基础》 实验五 简单嵌入式WEB 服务器实验
  2. MySQL 使用JOIN优化子查询
  3. js判断输入时间是否大于系统时间
  4. 使用javaScript实现简单倒计时功能
  5. JavaScript基础——理解变量作用域
  6. 12. Binary Tree Postorder Traversal &amp;&amp; Binary Tree Preorder Traversal
  7. Cron 表达式详解和案例
  8. 传智168期JavaEE就业班 day04-dom
  9. 點擊按鈕后彈出新頁面導致原頁面CSS失效
  10. Unity-Animator深入系列---StateMachineBehaviour初始化时间测试
  11. MVC每层的职责
  12. undefine refrence to &quot;*******&quot;
  13. linux使用tcpdump抓包工具抓取网络数据包,多示例演示
  14. Visual Studio2010 安装pthreads2.9.1
  15. 学习笔记02(随便看看mybatis源码)
  16. javascript 禁用 右键 按键 禁用开发者工具
  17. echarts图片保存
  18. 第十五节,卷积神经网络之AlexNet网络详解(五)
  19. codeforces411div.2
  20. TextView 中文文档

热门文章

  1. java 设计模式 -- 责任链模式
  2. Java 加载器
  3. Error executing DDL via JDBC Statement
  4. cmake学习之-configure_file
  5. 请实现一个函数用来匹配包括&#39;.&#39;和&#39;*&#39;的正则表达式。模式中的字符&#39;.&#39;表示任意一个字符,而&#39;*&#39;表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串&quot;aaa&quot;与模式&quot;a.a&quot;和&quot;ab*ac*a&quot;匹配,但是与&quot;aa.a&quot;和&quot;ab*a&quot;均不匹配
  6. ios美颜 调研 GPUImage GPUImageBeautifyFilter BeautifyFaceDemo
  7. Android App 启动页(Splash)黑/白闪屏现象产生原因与解决办法(转)
  8. EF6&amp;EFCore 注册/使用实体类的正确姿势
  9. NuGet管理工具安装
  10. Hihocoder #1602 : 本质不同的回文子串的数量 manacher + BKDRhash