题解：P1217 [USACO1.5] 回文质数 Prime Palindromes

看到这种水题能发题解，而且没复杂度优秀的，于是半整活一篇题解。

思路

首先，我们可以通过搜索来构造回文数，注意开头的数要从

1

开始，其它都能从

0

开始。还有个小优化，开头的只用枚举奇数，这样可以减去一部分偶数回文数，肯定非质数的情况。

然后枚举回文数的长度

n

，搜索时我们构造

\lfloor\frac{n+1}{2}\rfloor

长度的一个数，最后按照

n

奇偶性来构造回文数，具体请读者自己查看下方代码。

最后构造完看看这个数是否大于等于

a

且小于等于

b

，并且是质数。这里我使用了米勒拉宾质数判定法，配合快速幂可以做到

O(\log{n})

复杂度判断

n

是否质数，具体请读者自行搜索资料或题目。

有个小优化，如果这个长度的所有数都大于

b

，那么直接退出循环。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int qpow(int a,int k,int mod)
{
	a%=mod;
	int res=1;
	while(k)
	{
		if(k&1)res=res*a%mod;
		a=a*a%mod;
		k>>=1;
	}
	return res;
}
int p[12]={2,3,5,7,11,13,17,19,23,29,31,37};
bool millerrabin(int n)
{
	if(n<=2)return n==2;
	if(n<=37)
	{
		for(int i=0;i<12;i++)
		{
			if(n==p[i])return 1;
		}
		return 0;
	}
	int u=n-1,t=0;
	while(u%2==0)u/=2,t++;
	for(int i=0;i<12;i++)
	{
		int v=qpow(p[i],u,n);
		if(v==1)continue;
		int s=0;
		for(;s<t;s++)
		{
			if(v==n-1)break;
			v=(v*v)%n;
		}
		if(s==t)return 0;
	}
	return 1;
}
int a,b,i;
bool check(int x)
{
	int X=x,sum=0;
	while(x)
	{
		sum=sum*10+x%10;
		x/=10;
	}
	return X==sum;
}
void dfs(int x,int len,int now,int pos)
{
	if(x==len+1)
	{
		int sum=now;
		if(pos&1)sum/=10;
		while(now)
		{
			sum=sum*10+now%10;
			now/=10;
		}
		if(sum>=a&&sum<=b&&millerrabin(sum))cout<<sum<<endl;
		return ;
	}
	for(int i=((x==1)?1:0);i<=9;i+=((x==1)?2:1))dfs(x+1,len,now*10+i,pos);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b;
	for(i=1;i<10;i++)
	{
		if(qpow(10,i-1,LONG_LONG_MAX)>b)break;
		dfs(1,(i+1)/2,0,i);
	}
	return 0;
}

这份代码碾压所有非打表的方法。

但是米勒拉宾板子是紫。

题解：P1217 [USACO1.5] 回文质数 Prime Palindromes

文章操作

思路

代码

相关推荐

评论

题解：P1217 [USACO1.5] 回文质数 Prime Palindromes