将代码串进行打包，就是过程与函数。过程与函数调用自己则为递归。有一点小难但不要怕哦。

P1028 数的计算传播

题目描述

我们要求找出具有下列性质数的个数(包含输入的自然数n):

先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:

不作任何处理;
在它的左边加上一个自然数,但该自然数不能超过原数的一半;
加上数后,继续按此规则进行处理,直到不能再加自然数为止.

Code $O(n)$

Force 25% $O(n^n)$

递归是过不了的。。与Fibonacci相似。可以分析递归复杂度。

$f(n) = \sum_{i=1}^{n/2}f(i)+o(1)$

求上界的话，放缩一下：

$f(n) = nf(n-1)+o(1)$

显然，递推一下就有（$n!=O(n^n)$），比指数还吓人。。

$f(n) = O(n^n)$

#include <bits/stdc++.h>
using namespace std;

int f(int n){
    if(n == 1) return 1;
	int result = 0;
    for(int i = 1; i <= n/2; ++i)  //通项
        result += f(i);
    return result + 1;  //算上自己
}

int main(){
    int n; cin>>n;
    cout<<f(n);
}

Force+记忆剪枝 $O(n^2)+O(n)$

#include <bits/stdc++.h>
using namespace std;

int f_remember[1005];

int f(int n){
    if(n == 1) return 1;
	if(f_remember[n]) return f_remember[n];
	int result = 0;
    for(int i = 1; i <= n/2; ++i)
        result += f(i);
    return f_remember[n] = result + 1;  //记忆
}

int main(){
    int n; cin>>n;
    cout<<f(n);
}

迭代/传播 $O(n^2)+O(n)$

此方法相当于记忆剪枝的迭代版改写。

状态方程：（先求小，再求大）

$f(n) = \sum_{i=1}^{n/2}f(i)\\ f(1)=1$

注意到从递推式的基本项可以向上传播。

#include <bits/stdc++.h>
using namespace std;

int f[1005];

int main(){
    int n; cin>>n;
    f[1] = 1;
    for(int i = 2; i <= n; ++i){
        for(int j = 1; j <= i/2; ++j)  //通项
            f[i] += f[j];
        f[i] ++;  //算上自己
    }
    cout<<f[n];
}

递推优化 $O(n)+O(n)$

注意到，

$f(n) = \sum_{i=1}^{n/2}f(i)+o(1)\\ f(n-1) = \sum_{i=1}^{(n-1)/2}f(i)+o(1)$

显然每一步的求和中，存在大量的重复计算。

递推公式可以优化为：

$f(n) = SUM(n/2)+1\\ SUM(i) = SUM(i-1)+f(i)$

这时内部求和的$O(n)$变为分摊常数。同样可以采用递归或迭代方法。

当然也有另外一个更简洁的推导形式：（这里没有采用，不过更巧妙地利用了除以2的性质，但不容易想到，也不直观）

$f(2k+1) = f(2k)\\ f(2k) = f(2k-1)+f(k)\\$

记忆剪枝 $O(n)+O(n)$

#include <bits/stdc++.h>
using namespace std;

int f[1005], sum[505];

int F(int i); int Sum(int i);

int main(){
    int n; cin>>n;
    f[1] = sum[1] = 1;
    cout<<F(n);
}

int F(int i){
    if(f[i]) return f[i]; //剪枝
    return f[i] = Sum(i/2) + 1;  //利用赋值，记忆
}

int Sum(int i){
    if(sum[i]) return sum[i]; //剪枝
    return sum[i] = Sum(i - 1) + F(i);  //利用赋值，记忆
}

迭代传播 $O(n)+O(n)$

#include <bits/stdc++.h>
using namespace std;

int f[1005], sum[505];

int main(){
    int n; cin>>n;
    f[1] = 1;
    for(int i = 2; i <= n; ++i){
        sum[i/2] = sum[i/2 - 1] + f[i/2];
        f[i] = sum[i/2] + 1;
    }
    cout<<f[n];
}

就地传播 $O(n)+O(0.25n)$

前面两种的空间准确来讲其实是$O(n)+O(1.5n)$。通过就地可以进行空间优化。

理论上任何传播算法都可以做到就地，因为每一状态都只与紧邻的前一状态有关。

由于本题的两个传播公式相互耦合，同时实现两个状态的就地传播是不可能的。

可以理解为：当i取值较大时，sum的某一项sum[i]可以传播到f相对很远的两项f[2i],f[2i+1]，为了之后计算sum[2i]和sum[2i+1]，f的两项必须被动态缓存起来。可以预见，最多的缓存项可以达到$n/4$的规模。

但是，sum和f分别的就地传播，两种方案都可行。如下图所示：

1548417158739

再关注一下递推公式：

$f(n) = SUM(n/2)+1\\ SUM(i) = SUM(i-1)+f(i)$

于是我们可以由此写就地传播辣~～

sum就地 $O(n)+O(1.0n)$

#include <bits/stdc++.h>
using namespace std;

int f[1005], sum;

int main(){
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
		f[i] = sum + 1;
		if(i%2) sum += f[(i+1)/2];
	}
    cout<< f[n];
}

f就地 $O(n)+O(0.5n)$

#include <bits/stdc++.h>
using namespace std;

int f, sum[505];

int main(){
    int n; cin>>n;
    for(int i = 1; i <= n/2; i++){
		f = sum[i/2] + 1;
		sum[i] = f + sum[i - 1];
	}
    cout<< sum[n/2] + 1;
}

就地+队列 $O(0.5n)+O(0.25n)$

我们之前已经提到，f可以用动态缓存的方式记录。并且，每一个f[i]的调用都是先进先出的，因此可以采用队列。。

sum只要求到n/2就可以求出f[n]，sum只要求到n/4就可以求出f[n/2]。

因此，sum求到n/4（此时积累了n/4的缓存），然后卸载缓存到f[n/2]求得sum[n/2]，即可求出f[n]。如下图：

1548438031665

#include <bits/stdc++.h>
using namespace std;

queue<int> f; int sum = 0; //sum[0] = 0

int main(){
    int n; cin>>n;
    int i;
    
    f.push(1);  //initialize f as sum[1]
    for(i = 1; i <= (n >> 2); i++){
		sum += f.front(); f.pop();  //reserve f in queue buffer
		f.push(sum+1); f.push(sum+1);
	}
    for(     ; i <= (n >> 1); i++){
		sum += f.front(); f.pop();  //clear the buffer(maybe 1 element left sometime)
    }

    cout<< sum + 1;
}

P1036 选数决策树

题目描述

已知 n 个整数 x1,x2,…,xn，以及1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3, 4个整数分别为3,7,12,19时，可得全部的组合与它们的和为：

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29。

Code

Force $O(xC_n^k)$

由于k是变动的，想要直接循环k遍是不现实的。（难道递归不就是一种可变的嵌套循环吗？这样想的话，递归改写迭代的可行性就极其清晰了！——只有那种有限、确定的递归才能写成迭代形式。比如尾递归，消亡伴随诞生，因而有限递归）

还以为暴力是不能AC的。。。结果一次过。。

虽然k很小的时候也能强行写循环，但代码的泛化性能会非常差。（它在测试数据集上过拟合）

#include <bits/stdc++.h>
using namespace std;

int n, k;
int x[25];
int ans = 0;

bool is_prime(int number){
    for(int i = 2; i < number/2; i+=1)
        if(!(number % i)) return 0;
    return 1;
}

void combination(int i, int k, int sum_number){
    if( k==0 ){  //选完了所有的数
        if(is_prime(sum_number)){
        	ans++;
//	        cout<<"sum_number:"<<sum_number<<endl;
		}
        return ;
    }
    if(i >= n) return ;  //超出范围还没选完，作废
    //选还是不选，这是一个问题。。
    combination(i + 1, k , sum_number); //不选
    combination(i + 1, k - 1, sum_number + x[i]); //选，k - 1
}

int main(){
    cin>> n >> k;
    for(int i = 0; i < n; ++i)
        cin>> x[i];

    combination(0, k, 0);
    cout<<ans;
}

P1149 火柴棒等式模拟+打表

题目描述

给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0−9的拼法如图所示：

match

注意：

加号与等号各自需要两根火柴棍
如果A≠B，则A+B=C与B+A=C视为不同的等式(A,B,C>=0)
n根火柴棍必须全部用上

Code $O(n^2)$

C++ STL MultiSet类成员函数介绍及具体用法示例

Force $O(n^3)$

由于时间复杂度很高，只能求解小规模的问题。~~然而打擦边球通过了。。~~

#include <bits/stdc++.h>
using namespace std;

int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int Match(int number){ //convert num into match usage
	if(number <= 9) return match[number];
	int result = 0;
	while(number > 0){
		result += match[number%10];
		number /=10;
	}
	return result;
}

int main(){
    int n; cin>> n;
    
    multiset<int> possible_answer;
    for(int i = 0; i <= 711; i++)  //i的取值范围的上界是711才能完全保险
        for(int j = 0; j <= i; j++)
            for(int k = 0; k <= i; k++)
                if(i == j + k) possible_answer.insert(Match(i) + Match(j) + Match(k) + 4);

    cout<<possible_answer.count(n);
}

Force+剪枝 $O(n^2)$

由于统计的是等式的数量，根本没必要在大量的不等式上浪费时间，可以直接有k=i-1。

#include <bits/stdc++.h>
using namespace std;

int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int Match(int number){ //convert num into match usage
	if(number <= 9) return match[number];
	int result = 0;
	while(number > 0){
		result += match[number%10];
		number /=10;
	}
	return result;
}

int main(){
    int n; cin>> n;
    
    multiset<int> possible_answer;
    for(int i = 0; i <= 711; i++)  //i的取值范围的上界是711才能完全保险
        for(int j = 0; j <= i; j++)
            possible_answer.insert(Match(i) + Match(j) + Match(i - j) + 4);

    cout<<possible_answer.count(n);
}

打表 $O(1)+O(n)$

作者: sochiji
更新时间: 2018-07-14 14:49

在Ta的博客查看

由于数据范围很小，答案可以直接预先算出来。。（~~我们之前的方案也不过是在线打表。。~~）

打表程序：

#include <bits/stdc++.h>
using namespace std;

int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int Match(int number){ //convert num into match usage
	if(number <= 9) return match[number];
	int result = 0;
	while(number > 0){
		result += match[number%10];
		number /=10;
	}
	return result;
}

int main(){
    multiset<int> possible_answer;
	    for(int i = 0; i <= 711; i++)  //i的取值范围的上界是711才能完全保险
	        for(int j = 0; j <= i; j++)
	            possible_answer.insert(Match(i) + Match(j) + Match(i - j) + 4);
	
	int n = 0;
	cout<<"int table = {";
	while(n <= 28){
	    cout<<possible_answer.count(n); 
		if(n!=28) cout<<','; 
		n++;
	}
	cout<<"};";
}

OJ程序：

#include <bits/stdc++.h>
using namespace std;
int n;
int table[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39,38,65,86,128,178,295,430,574};

int main(){
	cin>>n;
	cout<<table[n];
}

*P1217 [USACO1.5]回文质数 Prime Palindromes 素数筛法+回文模拟

题目描述

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

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

说明

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

USACO Training Section 1.5

产生长度为5的回文数:

for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }

Code $\approx O(n)$

重用一下P1036 选数题的代码。。

Force $O((b-a)logn)$

普通判断 33% $O((b-a)n)$

#include <bits/stdc++.h>
using namespace std;

int a, b;
int ans = 0;

bool is_prime(int number){  //O(n)
    for(int i = 2; i < number/2; i+=1)
        if(!(number % i)) return 0;
    return 1;
}

bool is_palindrome(int number){  //O(logn)
    vector<int> nums;
    while(number > 0){
        nums.push_back(number%10); number/=10;
    }
    int i = 0, j = nums.size() - 1;
    while(i < j)
        if(nums[i++] != nums[j--]) return 0;
    return 1;
}

void generate(int a, int b){  //O(b-a)
    if(is_prime(a) && is_palindrome(a)) cout<<a<<endl;
    if(a == b) return ;
    generate(a + 1, b);  //尾递归 
}

int main(){
    cin>> a >> b;
    generate(a, b);
}

改进`is_prime` 66% $O((b-a)\sqrt n)$

for循环条件改为i*i<=number即可。（避免重复计算，比如对于6，2,3和3,2只须判断一次即可）

短路优化 55% $O((b-a)logn)$

先判断is_prime的复杂度是O(n)，而该表达式有短路特性，观察到is_palindrome仅需O(logn)。交换一下两个函数的位置：

1 2	for(int i = a; i <= b; ++i) if(is_palindrome(i) && is_prime(i)) cout<<i<<endl;

但实际测试效果，时间复杂度反而增加了。orz

初步估计，是is_prime内部的短路对整个测试影响更大，大量is_prime运行时接近O(1)，比如偶数。

埃氏筛法 88% $O(nloglogn)+O(n)$

Force中的尾递归可改写为迭代形式。

1 2	for(int i = a; i <= b; ++i) if(is_prime(i) && is_palindrome(i)) cout<<i<<endl;

开辟额外空间O(n)。先筛出所有素数，这样is_prime的复杂度会保证降到O(1)。

埃拉托斯特尼筛法

初始化：默认所有数为素数（也可以附加设定0，1不是素数）
从i=2开始，遍历最近的素数（到根号n为止）
- 从j=i*i开始，步长为i，遍历并标记合数

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 100000005
int a, b;
int ans = 0;
bool prime[MAX_N];

void Eratosthenes(int b){  //O(nloglogn)
	prime[0] = prime[1] = 0;
	for(int i = 2; i <= b; ++i)
		prime[i] = 1;
	for(int i = 2; i*i <= b; ++i)
		if(prime[i])
			for(int j = i*i; j <= b; j+=i){
				prime[j] = 0; 
			}
}

bool is_prime(int number){  //O(1)
    return prime[number];
}

bool is_palindrome(int number){  //O(logn)
    vector<int> nums;
    while(number > 0){
        nums.push_back(number%10); number/=10;
    }
    int i = 0, j = nums.size() - 1;
    while(i < j)
        if(nums[i++] != nums[j--]) return 0;
    return 1;
}

int main(){
    cin>> a >> b;
	Eratosthenes(b);
    for(int i = a; i <= b; ++i)
    	if(is_prime(i) && is_palindrome(i)) cout<<i<<endl;
}

循环还是要加括号。。否则会出现奇怪的错误。。

*复杂度$O(nloglogn)$的证明：（~~证了等于没证~~）

本质是对数列和$S_n$的渐进估计：（p取不大于n的所有素数）

$S_n=\frac{n}{p_{1} }+\frac{n}{p_{2} }+...+\frac{n}{p_{i} }+...+\frac{n}{p_{max} }=O({\color{red}{?} })$

根据Mertens’ 2nd theorem:

$\lim_{n→∞}{\left(\sum_{p≤n} \frac{1}{p}−lnlnn-M\right)}=0$

代入数列$S_n$，

$\lim_{n→∞}{\left(\frac{S_n}{n}−lnlnn-M\right)}=0\\ \lim_{n→∞}{\left(\frac{S_n}{n}\right)}=O(lnlnn+M)\\ \lim_{n→∞}S_n=O(nlnlnn+Mn)=O(nlnlnn)$

注意如果p取不大于根号n的所有素数，只能获得很小的常数级优化：$O(nlnln\sqrt n=O(nln(0.5lnn)))$

欧拉筛法 88% $\approx O(n)+O(n+\frac{n}{logn})$

埃拉托色尼筛法的复杂度估计与改进及线性时间筛法简介

线性筛法求素数的原理与实现

埃氏筛法和欧拉筛法的区别

自制暴力区间素数筛法的由来（这个概率筛也是666，以及多规模筛法）

欧拉筛法之所以效率高，是因为质数单独一个存放到一个数组中，这样可以使每个合数都能被其最小质数筛掉。

线性筛法(欧拉筛法)求素数

埃氏筛法、欧拉筛法、积性函数线性筛与莫比乌斯反演

欧拉线性筛法求素数(顺便实现欧拉函数的求值)

任何合数都能表示成一系列素数的积。

这只菜鸟总算搞懂了线性筛素数

~~看了好多资料依然一脸懵逼~~。。

说实话就算一亿的$loglog10^8$也只有3，已经极度接近线性了，~~这道题确定不是卡常数么~~。

注意到质因子较多的合数会被反复标0（累计$O(loglogn)$？），这显然是重复的工作。

而每一个合数的最小/最大质因子都是唯一的。

枚举每一个数i
- 若i是素数，先存入素数表p_numbers（显然素数表单增）
- 用J遍历素数表（生成关于i*J的乘法元集，并筛掉）
  - 先筛掉i*J（默认筛）
  - 若i%J==0（即i*J=A*J*J）
    - 记J’>J是素数表中任意一个比J更大的素数
    - 接下来要筛的任何一个对象i*J'=(A*J)*J'=(A*J')*J，都会在之后被一个比i更大的i'=(A*J')默认筛掉
      - 而且只要被筛对象合法，i'=(A*J')<i*J'肯定会被遍历到
      - 而且能保证不会重复筛
        
        假设i'*J'之前被i筛过，那么必然有i'*J'=(i*J)*J'=i*(J*J')，而(J*J')是合数，矛盾
    - 显然无须继续遍历，提前退出即可

自己动手写一下，~~立马就理解了~~。~~真的很神奇，然而还是很懵逼~~。能保证合数总是被它最大的因子/最小的质因子筛掉。

int p_numbers[MAX_N], size = 0; //reserve primes

void Euler(int Length){  //about O(n)
	prime[0] = prime[1] = 0;
	for(int i = 2; i <= Length; ++i) prime[i] = 1; //initialize all as true
	for(int i = 2; i <= Length; ++i){
		if(prime[i]){
            p_numbers[size++] = i;
        }
        for(int j = 0; j <size && i*p_numbers[j] < Length; j++){
            prime[ i*p_numbers[j] ] = 0;  //sieve i*p_numbers[j]
            if(i % p_numbers[j] == 0)  //special
               break;
        }
	}
}

欧拉筛法只是极度极度极度接近线性，并不真是线性。（但是在筛操作的意义上是绝对线性的）

printf("%.2f", (double)clock()/CLOCKS_PER_SEC);可以用来显示运行时间。

p_numbers[MAX_N]的MAX_N最小可以换为MAX_N/ln(MAX_N)。（$\pi(x)=\cfrac{x}{lnx}$）

回文数整流

作者: SocietyNiu
更新时间: 2018-02-04 18:04

在Ta的博客查看

在这里首先要知道：1.偶数位数回文数（除11）必定不是质数（自行百度），所以只要运行到10000000。2.偶数肯定不是质数。这样至少排除一半多的数据量。3，你回文数已经判断出来了，在此中判断即可。

程设刷题 | 大范围内高效查找回文质数（回文数猜想）

道理很简单：如果一个回文素数的位数是偶数，则它的奇数位上的数字和与偶数位上的数字和必然相等；根据数的整除性理论，容易判断这样的数肯定能被11整除，所以它就不可能是素数。

除了 11 以外的回文质数一定是奇数位数吗？如果是如何证明？

~~原来考察的重点在整流上~~。传参改为：

Eratosthenes(b>10000000 ? 10000000: b);
Euler(b>10000000 ? 10000000: b);
两个都可以擦边过。（耗时很接近）

相当于一个整流函数。类似ReLU。

区间素数筛法 $O(\sqrt n+(b-a)loglogn)+O(\sqrt n+(b-a))$

可能准确的复杂度是在根号n和n之间的。。思考得不太准确orz

貌似又有区间素数筛法，主要思想是利用区间约束降低时间复杂度。

要获得[a,b]的素数，我们最少只需要求出[0,√b]内的素数。（因为[a,b]内的任意合数必定有[0,√b]的质因子）

构造[0,√b]和[a,b]两个区间，如果区间很小，那么在时空复杂度上会有巨大优势。

但是本题的区间往往很大。。。所以这个方法的效果并不好。。甚至会慢许多。。

然后先构造[0,√b]的素数表，利用素数表来筛去[a,b]中的合数。

埃氏筛法、区间筛法(求素数个数)

如果[0,√b]用埃式筛法，复杂度就是$O(\sqrt nloglogn+(b-a)loglogn)+O(\sqrt n+(b-a))$

如果[0,√b]用欧拉筛法，复杂度就是$O(\sqrt n+(b-a)loglogn)+O(\sqrt n+(b-a))$

~~大概是这样。。~~

下面是程序：

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 100000005
int a, b;
int ans = 0;
bool prime[MAX_N]; // [0, sqrt(b)]
bool primes_AB[MAX_N];  // [a,b]
int p_numbers[MAX_N], size = 0; // reserve primes [0, sqrt(b)]

void Eratosthenes(int a, int b){  //O((b-a)loglog(b-a))
    for(int i = 0; i <= b - a; ++i)
        primes_AB[i] = 1;  //initialize [a,b]
    
    for(int i = 0; i <= b - a; ++i){
        for(int j = 0; j < size; ++j){
            if((a+i) == p_numbers[j]) break;
			if((a+i) % p_numbers[j] == 0){
                primes_AB[i] = 0;
                break;
            }
        }
    }
}

void Eratosthenes(int Length){  //O(nloglogn)
    prime[0] = prime[1] = 0;
    for(int i = 2; i <= Length; ++i) prime[i] = 1;
    
    for(int i = 2; i*i <= Length; ++i)
        if(prime[i]){
        	for(int j = i*i; j <= Length; j+=i){
                prime[j] = 0;
            }
		}
	for(int i = 2; i <= Length; ++i){
		if(prime[i]) p_numbers[size++] = i;
	}
}

void Euler(int Length){  //~~O(n)
	prime[0] = prime[1] = 0;
	for(int i = 2; i <= Length; ++i) prime[i] = 1; //initialize all as true
	
	for(int i = 2; i <= Length; ++i){
		if(prime[i]){
            p_numbers[size++] = i; //remember
        }
        for(int j = 0; j <size && i*p_numbers[j] < Length; j++){
            prime[ i*p_numbers[j] ] = 0;
            if(i % p_numbers[j] == 0)
               break;
        }
	}
}

bool is_prime(int Number){
    return primes_AB[Number - a];
}


bool is_palindrome(int number){  //O(logn)
    vector<int> nums;
    while(number > 0){
        nums.push_back(number%10); number/=10;
    }
    int i = 0, j = nums.size() - 1;
    while(i < j)
        if(nums[i++] != nums[j--]) return 0;
    return 1;
}

int main(){
    cin>> a >> b;
    int sqrt_b = int(sqrt(b>10000000 ? 10000000: b));

	Euler(sqrt_b);
//    Eratosthenes(sqrt_b);
    
    Eratosthenes(a, b); // [a, b]

    for(int i = a; i <= b; ++i){
    	if(is_prime(i) && is_palindrome(i)) cout<<i<<endl;
	}
    	
}

好像洛谷有一道题是专门用这个方法的。。

P1835 素数密度_NOI导刊2011提高（04）

米勒-拉宾素性检验

打表 $O(x)+O(x)$

打表法就是将题目中需要的答案集合提前算出来，存到代码里，根据题目所需取答案，这种方法通常只需要将程序挂着，在表打完后进行加工，最终取答案程序时间复杂度为O(1)，空间复杂度为O(n)(n为答案规模)； ——沃兹·基朔德

x是所有回文质数的数量。

打表程序 $O(nlogn)$

#include <bits/stdc++.h>
using namespace std;

int a, b;
int ans = 0;

bool is_prime(int number){
    for(int i = 2; i < number/2; i+=1)
        if(!(number % i)) return 0;
    return 1;
}

bool is_palindrome(int number){
    vector<int> nums;
    while(number > 0){
        nums.push_back(number%10); number/=10;
    }
    int i = 0, j = nums.size() - 1;
    while(i < j)
        if(nums[i++] != nums[j--]) return 0;
    return 1;
}

int main(){
    cout<<"int table[] = {";
    for(int i = 5; i <= 10000000; ++i)
    	if(is_palindrome(i) && is_prime(i)) cout<<i<<',';
    cout<<"};";
}

OJ程序：

#include <bits/stdc++.h>
using namespace std;
int table[] = {5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};
int a, b;
int main(){
    cin>>a>>b;
    int i = 0;
    while(table[i] < a) i++;
    while(table[i] <= b && table[i] != 0) cout<<table[i++]<<endl;
}

二分打表 $O(logx)+O(x)$

显然储存的序列是天然有序的，因而可以二分减治/剪枝。。（~~大约是O(logx)吧~~）

先求一下table的长度：779。

#include <bits/stdc++.h>
using namespace std;
int table[] = {5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};
int a, b;

int lower_bound(int a, int begin, int end){  //返回小于等于a的table元素的最大下标 
	while(begin < end - 1){
		int mid = (begin + end) >> 1;
		if(table[mid] <= a) begin = mid;
		else end = mid;
	}
	return begin;
}

int main(){
    cin>>a>>b;
    int begin = lower_bound(a, 0, 779); 
	int end =lower_bound(b, begin, 779);
	
	while(table[begin] < a) begin++; //微调一下 
	while(table[end] > b) end--;
    
    for(int i = begin; i <= end; ++i)
		cout<<table[i]<<endl;
}

c++貌似有标准函数lower_bound()。。

回文数生成【正解】

发现了吗。。到现在为止根本没有用到提示嘛！！！！

这就是真666666666666666了。

偶然在提交记录里看到一个最优解筛选。。。跪了跪了。不用打表也能0ms这么强！！！！！

然后在题解往后翻，果然翻到了。。

作者: 风休住
更新时间: 2018-11-22 18:45

在Ta的博客查看

由于构造回文数时只需枚举前半部分回文数，因此时间效率大大提高。~~这才叫高性能好不~~

原来提示里边的Hint 1: Generate the palindromes and see if they are prime.大有深意。。。

本题的重点其实是回文数而非质数。

求5 ~ 1000000000内的回文素数

恼人的’素数回文’

POJ 3247:回文素数—外表甜美内心却极为暴力的萝莉题

总的来说就是：

需要找的数既是回文数又是质数，虽然两位都不是好惹的主，但柿子得挑软的捏，相比之下，质数这个柿子要硬一些，如果先找出高达9位数以内的质数，计算量太大必然会超时。所以不妨先确认一个思路：

先找出n位数中所有的回文数，然后再来判断其是不是质数。

1
2

以后再写~~~

P1028 数的计算 传播

题目描述

Code $O(n)$

Force 25% $O(n^n)$

Force+记忆剪枝 $O(n^2)+O(n)$

迭代/传播 $O(n^2)+O(n)$

递推优化 $O(n)+O(n)$

记忆剪枝 $O(n)+O(n)$

迭代传播 $O(n)+O(n)$

就地传播 $O(n)+O(0.25n)$

sum就地 $O(n)+O(1.0n)$

f就地 $O(n)+O(0.5n)$

就地+队列 $O(0.5n)+O(0.25n)$

P1036 选数 决策树

题目描述

Code

Force $O(xC_n^k)$

P1149 火柴棒等式 模拟+打表

题目描述

Code $O(n^2)$

Force $O(n^3)$

Force+剪枝 $O(n^2)$

打表 $O(1)+O(n)$

*P1217 [USACO1.5]回文质数 Prime Palindromes 素数筛法+回文模拟

题目描述

说明

Code $\approx O(n)$

Force $O((b-a)logn)$

普通判断 33% $O((b-a)n)$

改进is_prime 66% $O((b-a)\sqrt n)$

短路优化 55% $O((b-a)logn)$

埃氏筛法 88% $O(nloglogn)+O(n)$

欧拉筛法 88% $\approx O(n)+O(n+\frac{n}{logn})$

回文数整流

区间素数筛法 $O(\sqrt n+(b-a)loglogn)+O(\sqrt n+(b-a))$

打表 $O(x)+O(x)$

二分打表 $O(logx)+O(x)$

回文数生成【正解】

P1028 数的计算传播

P1036 选数决策树

P1149 火柴棒等式模拟+打表

改进`is_prime` 66% $O((b-a)\sqrt n)$