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

· · 题解

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

思路

首先，我们可以通过搜索来构造回文数，注意开头的数要从 1 开始，其它都能从 0 开始。还有个小优化，开头的只用枚举奇数，这样可以减去一部分偶数回文数，肯定非质数的情况。

然后枚举回文数的长度 n，搜索时我们构造 \lfloor\frac{n+1}{2}\rfloor 长度的一个数，最后按照 n 奇偶性来构造回文数，具体请读者自己查看下方代码。

最后构造完看看这个数是否大于等于 a 且小于等于 b，并且是质数。这里我使用了米勒拉宾质数判定法，配合快速幂可以做到 O(\log{n}) 复杂度判断 n 是否质数，具体请读者自行搜索资料或题目。

有个小优化，如果这个长度的所有数都大于 b，那么直接退出循环。

代码

#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;
}

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

但是米勒拉宾板子是紫。