题目链接

传送门

题目描述

因为 151 既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 是回文质数。

写一个程序来找出范围 [a,b] (5 \le a < b \le 100,000,000)a,b( 一亿)间的所有回文质数。

输入格式

第 1 行: 二个整数 a 和 b .

输出格式

输出一个回文质数的列表,一行一个。

输入输出样例

输入

5 500

输出

5
7
11
101
131
151
181
191
313
353
373
383

想说的话

是OI限制了我的想象力 还是我tm现在实在太菜了。。。

题解

先说不加强版的吧 数据范围是1e9 显然直接搞有点慌
所以我们一定可以有什么奇技淫巧 巧妙方法
我们利用这个数的特点 可以看出 偶数位数的回文数一定是11的倍数(判断11倍数的方法是奇数位数字之和减去偶数位数字之和)
然后这个题的数据范围直接到1e8 开心一波线性筛然后加上暴力判断回文数 这题就水过去了
值得注意的是11本身是一个质数 这也是唯一的偶数位数的回文质数

然后加强版是HITOJ上的1004 数据范围变成了1e10
WDNMD? 我慌了啊 这怎么线性筛
我一看时间 5s的限制?
我甚至想暴力埃氏筛走一波(
不不不不不能这样

线性筛不行了 我们考虑全新的做法
既然不能预处理素数 那我们为什么不能预处理回文数(手动捂脸)
然后我们对于预处理出来的回文数进行埃氏筛就可以了
当时我居然还想到PR判断素数 但是我早就忘了怎么写了hhh
复杂度证明的话可以发现奇数位数回文数的个数是1e6级别的
这样nsqrt(n)加上一点常数的复杂度是完全正确的
事实证明我0.76s就过了
这玩意绝度就是OI限制了我的想象力
因为OI给人的习惯就是预处理素数 没什么例外好像QAQ

代码——方法1

代码——方法2