湘大 XTU OJ 1345 素数字符串题解：欧拉筛法前缀和 ‘\0‘ sprintf-Toy模板网

这篇具有很好参考价值的文章主要介绍了湘大 XTU OJ 1345 素数字符串题解：欧拉筛法前缀和 ‘\0‘ sprintf。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链接

素数字符串

题目

题目描述

我们将素数从小到大依次书写，可以得到一个字符串"23571113⋯"，已知一个数码d(0≤d≤9),求字符串在区间[L,R]之间的多少个d?

输入

第一行是一个整数T(1≤T≤10000)，表示样例的个数。每个样例是一行，为3个整数，区间L,R,(1≤L≤R≤1000000)和数码d。区间从1开始计数。

输出

每行输出一个样例的结果。

样例输入

2
1 8 1
1 8 4

样例输出

3
0

代码

#include<iostream>
#include<cstring>

using namespace std;

bool isprime[2100000];//这个为什么要2100000，开成1100000，为啥不行，或者说这个要怎么
//设置，我开大一点就超出空间限制了
int prime[110000];
int res[11][1100000];

void oula()
{
	int cnt=0;
	memset(isprime,true,sizeof(isprime));
	
	isprime[0]=isprime[1]=false;
	
	for(int i=2;i<2100000;i++)
	{
		if(isprime[i])	prime[++cnt]=i;//从1开始计数
		
		for(int j=1;j<=cnt&&i*prime[j]<2100000;j++)
		{
			isprime[i*prime[j]]=false;
			if(i%prime[j]==0)	break;
		}
	}
}

void prime_table()
{
	char s[11];
	int count=0;
	for(int i=1;prime[i]!=0;i++)
	{
		memset(s,'\0',sizeof(s));
		sprintf(s,"%d",prime[i]);
		
		for(int j=0;s[j]!='\0';j++)
			for(int k=0;k<=9;k++)
				if(s[j]==(char)(k+48))	res[k][count+j+1]=1;
		
		count+=strlen(s);
	}
}

void front_sum()
{
	for(int i=0;i<=9;i++)
		for(int j=1;j<=1100000;j++)
			res[i][j]+=res[i][j-1];
}

int main()
{
	oula();
	prime_table();
	front_sum();
	
	int t;
	scanf("%d",&t);
	
	while(t--)
	{
		int l,r,d;
		scanf("%d%d%d",&l,&r,&d);
		
		printf("%d\n",res[d][r]-res[d][l-1]);
	}
	
	return 0;
}

总结

1. '\0'是什么意思：

'\0'表示空字符，是判断字符串结束的标志，它的ASCII数值是0

#include<iostream>

using namespace std;

int main()
{
	printf("%d",'\0');
	
	return 0;
}

参考链接：c语言中‘\0‘ ，‘0‘， “0“ ，0的区别

2.欧拉筛法

#include<iostream>
#include<cstring>

using namespace std;

const int N=1e8;

bool isprime[N];
int prime[N];

int n,cnt;

void oula()
{
	memset(isprime,true,sizeof(isprime));
	
	isprime[0]=isprime[1]=false;
	
	//cnt=0;
	
	for(int i=2;i<=n;i++)
	{
		if(isprime[i])	prime[++cnt]=i;
		
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
		{
			isprime[i*prime[j]]=false;
			if(i%prime[j]==0)	break;
		}
	}
}

int main()
{
	scanf("%d",&n);
	
	oula();
	
	for(int i=1;i<=cnt;i++)
		printf("%d ",prime[i]);
	
	return 0;
}

参考链接：【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明

3.sprintf函数的使用

相当于把双引号里面的内容输出到数组里面保存，并且是把一个一个字符存在数组里面

#include<iostream>
#include<stdio.h>

using namespace std;

int main()
{
	int a=12345;
	char s[10];
	
	sprintf(s,"%d",a);
	
	printf("%s",s);
	
	printf("\n");
	
	printf("%c",s[0]);
	
	return 0;
}

比如说这个代码是把整型变量a存在字符串数组s里面

参考链接：2.C语言基础-sprintf函数用法

4. i++和++i是有区别的，i++是使用自增之前的数值，++i是使用自增之后的数值，前缀和一般从1开始计数比较方便，所以

res[k][count+j+1]=1;

加上一，从1开始计数

5.这个分为三个函数，第一个函数是欧拉筛法，第二个函数是素数打表，第三个函数是求前缀和，前缀和的公式：前缀和

6.欧拉筛法前面说了，是一个时间复杂度是线性的模板

7.素数打表，遍历每一个素数，把每一个素数转换成数组元素，意思是12345转换成‘1’‘2’‘3’‘4’‘5’ 存在数组里面，然后遍历这个数组，再遍历0-9每一个数字，如果相等就把计数的二维数组的对应位置标记为1，在遍历数组，遍历0-9循环外面，计算一个count，等于这个数组实际使用到的长度，这样可以使得标记的位置不会重叠，二维数组的指针会不断的往后移动（可以这么理解）

8.前缀和，二维数组行列，不看行就是普通的前缀和，对每一列使用前缀和的预处理

9.最后调用前缀和公式就可以解决这个题目

$湘大 XTU OJ 1345 素数字符串题解：欧拉筛法前缀和 ‘\0‘ sprintf,算法竞赛,湘大 XTU OJ,c++,算法,开发语言$