题目:Click here

题意:π(n)表示不大于n的素数个数,rub(n)表示不大于n的回文数个数,求最大n,满足π(n) ≤ A·rub(n)。A=p/q;

分析:由于这个题A是给定范围的,所以可以先暴力求下最大的n满足上式,可以想象下随着n的增大A也在增大(总体正相关,并不是严格递增的),所以二分查找时不行的,所以对给定的A,n是一定存在的。这个题的关键就是快速得到素数表最好在O(n)的时间以内。(杭电15多校的一个题也用到了这个算法点这里查看)

 #include <bits/stdc++.h>
using namespace std;
const int M = +; double p, q;
bool prime[M];
int ans, pri, pal;
void getprime( ) { // 类似筛选法求素数 打表
prime[] = false;
for( int i=; i<M; i++ ) {
if( !prime[i] ) continue;
prime[i] = true;
for( int j=; j*i<M; j++ )
prime[i*j] = false;
}
} bool palindromic( int n ) { // 判断回文数
int fn = ;
int aun = n;
while( aun ) {
fn *= ;
fn += aun%;
aun /= ;
}
return fn == n ;
} int main() {
memset( prime, true, sizeof(prime) );
getprime( );
while( ~scanf("%lf%lf", &p, &q ) ) {
double A = p/q;
pri = pal = ;
for( int i=; i<M; i++ ) {
pri += prime[i];
pal += palindromic(i);
if( pal*p/q >= pri )
ans = i;
}
printf("%d\n", ans );
}
return ;
}

最新文章

  1. 本周PSP流程进度
  2. Ios学习之容器的理解
  3. Intelij IDEA 2016.3安装mybatis插件并激活教程
  4. nginx location语法使用说明
  5. c++获取系统时间(引用别人的博文)
  6. codevs 1299 线段树 区间更新查询
  7. linux 课后作业
  8. ntpServer搭建用以进行时间同步
  9. [iOS基础控件 - 6.4] 汽车品牌展示 Model嵌套/KVC/TableView索引
  10. 安卓模拟器还是&quot;genymotion&quot;最靠谱.
  11. Linux 常用系统命令-20160504
  12. JDBC数据库连接
  13. windows10 配置 华为vpn客户端
  14. springmvc之单元测试(MockMvc)-独立测试
  15. [HAOI 2008]糖果传递
  16. mybatis基础(上)
  17. excel合并
  18. android 可以精确到秒级的时间选择器
  19. (转)thymeleaf中的判断总结
  20. ps切图插件

热门文章

  1. BZOJ 2733: [HNOI2012]永无乡(treap + 启发式合并 + 并查集)
  2. MQTT协议详解一
  3. 获取执行计划——EXPLAN PLAN
  4. 驱动之路四------adc驱动(input设备)
  5. Linux C网络编程学习笔记
  6. linux cpu亲和性设置
  7. javascript收集整理
  8. Android手机安全软件的恶意程序检测靠谱吗--LBE安全大师、腾讯手机管家、360手机卫士恶意软件检测方法研究
  9. Qt5位置相关函数异同详解(附源码)
  10. 12个高矮不同的人,排成两排(catalan数)