新手村-过程函数与递归*

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

P1028 数的计算 传播

题目描述

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

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

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

Code $O(n)$

Force 25% $O(n^n)$

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

求上界的话,放缩一下:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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)$

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

状态方程:(先求小,再求大)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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)$

注意到,

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

递推公式可以优化为:

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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​$的规模。

但是,sumf分别的就地传播,两种方案都可行。如下图所示:

1548417158739

再关注一下递推公式:

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

sum就地 $O(n)+O(1.0n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
#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)$
1
2
3
4
5
6
7
8
9
10
11
12
13
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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很小的时候也能强行写循环,但代码的泛化性能会非常差。(它在测试数据集上过拟合)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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

注意:

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

Code $O(n^2)$

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

Force $O(n^3)$

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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的博客查看

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

打表程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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程序:

1
2
3
4
5
6
7
8
9
#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的回文数:

1
2
3
4
5
6
7
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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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即可。(避免重复计算,比如对于62,33,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)。

埃拉托斯特尼筛法

埃拉托斯特尼筛法

  • 初始化:默认所有数为素数(也可以附加设定01不是素数)
  • i=2开始,遍历最近的素数(到根号n为止)
    • j=i*i开始,步长为i,遍历并标记合数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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的所有素数)

根据Mertens’ 2nd theorem:

代入数列$S_n​$,

注意如果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')是合数,矛盾
        • 显然无须继续遍历,提前退出即可

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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))$

大概是这样。。

下面是程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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)​$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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程序:

1
2
3
4
5
6
7
8
9
10
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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


以后再写~~~

0%