Codeforces Round #315 (Div. 2C) 568A Primes or Palindromes? 素数打表+暴力
2024-10-19 04:35:06
题目: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 ;
}
最新文章
- 本周PSP流程进度
- Ios学习之容器的理解
- Intelij IDEA 2016.3安装mybatis插件并激活教程
- nginx location语法使用说明
- c++获取系统时间(引用别人的博文)
- codevs 1299 线段树 区间更新查询
- linux 课后作业
- ntpServer搭建用以进行时间同步
- [iOS基础控件 - 6.4] 汽车品牌展示 Model嵌套/KVC/TableView索引
- 安卓模拟器还是";genymotion";最靠谱.
- Linux 常用系统命令-20160504
- JDBC数据库连接
- windows10 配置 华为vpn客户端
- springmvc之单元测试(MockMvc)-独立测试
- [HAOI 2008]糖果传递
- mybatis基础(上)
- excel合并
- android 可以精确到秒级的时间选择器
- (转)thymeleaf中的判断总结
- ps切图插件