首页 > ACM题库 > HDU-杭电 > HDU 1431 素数回文-数论-[解题报告] C++
2013
12-10

HDU 1431 素数回文-数论-[解题报告] C++

素数回文

问题描述 :

xiaoou33对既是素数又是回文的数特别感兴趣。比如说151既是素数又是个回文。现在xiaoou333想要你帮助他找出某个范围内的素数回文数,请你写个程序找出 a 跟b 之间满足条件的数。(5 <= a < b <= 100,000,000);

输入:

这里有许多组数据,每组包括两组数据a跟b。

输出:

对每一组数据,按从小到大输出a,b之间所有满足条件的素数回文数(包括a跟b)每组数据之后空一行。

样例输入:

5 500

样例输出:

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


直接DFS深度搜索一下就可以把所有回文数给算出来了。而且回文数,我只需要知道前面一半就可以得到后面的一段了。
然后预处理完成后,直接调用upper_bound或者lower_bound之类的函数,二分计算出答案

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>

using namespace std;

int ans[20000],len=0;
int temp[20];

int change(int dep,int dk)
{
	int i,ret=0;
	if(dk==0)
	{
		for(i=1;i<=dep;i++)
			ret=ret*10+temp[i];
		for(i=dep;i>=1;i--)
			ret=ret*10+temp[i];
	}
	else
	{
		for(i=1;i<dep;i++)
			ret=ret*10+temp[i];
		ret=ret*10+temp[dep];
		for(i=dep-1;i>=1;i--)
			ret=ret*10+temp[i];
	}
	return ret;
}

bool judge(int x)
{
	int i;
	if(x<=1)
		return false;
	for(i=2;i*i<=x;i++)
		if(x%i==0)
			return false;
	return true;
}

void dfs(int id,int dep,int dk)
{
	int i;
	if(id>dep)
	{
		int x=change(dep,dk);
		if(judge(x))
			ans[len++]=x;
		return;
	}
	for(i=0;i<=9;i++)
	{
		if(id==1&&i==0)
			continue;
		temp[id]=i;
		dfs(id+1,dep,dk);
	}
}

void init()
{
	int l,k;
	ans[len++]=2;
	ans[len++]=3;
	ans[len++]=5;
	ans[len++]=7;
	for(l=2;l<=9;l++)
	{
		k=(l+1)/2;
		if(l&1)
			dfs(1,k,1);
		else
			dfs(1,k,0);
	}
}

int main()
{
	int i;
	init();
	int a,b,x,y;
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		x=upper_bound(ans,ans+len,a)-ans;
		y=upper_bound(ans,ans+len,b)-ans;
		for(i=x-1;i<=y-1;i++)
			printf("%d\n",ans[i]);
		printf("\n");
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/xieshimao/article/details/6885017


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1