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

这道题目让我意识到了卡常的重要性

直接暴力枚举

#include<bits/stdc++.h>
using namespace std;
int p[10000000];
int top=1;
bool vis[100000000];
inline void prime(register int a,register int b)
{
    for(register int i=2;i<=b;i++)
    {
        if(vis[i]==0)
        {
            if(i>=a)p[top]=i,top++; 
            for(register int o=i;o<=b;o+=i)vis[o]=1;
        }
    }
}
inline int check(register int k)
{
    register string s;
    stringstream stream;
    stream<<k;
    stream>>s;
    register int l=s.length();
    register int flag=1;
    for(register int i=0;i<l/2;i++)
    if(s[i]!=s[l-i-1])
    {
        flag=0;
        break;
    }
    return flag;
}
int main()
{
    int a,b;
    cin>>a>>b;
    prime(a,b);
    for(register int i=1;i<top;i++)
    {
        if(check(p[i]))
        {
            printf("%d\n",p[i]);
        }
    }
}

最后一个点十一秒才出

于是仔细观察代码，

1. i++改为++i
2. o2o3优化
3. register
4. inline
5. printf（）
6. std::
7. break剪枝
8. 位运算
9. 找到潜藏规律100000000里的最后一个回文质数是9989899
10. 质数筛法优化

于是

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
int p[10000000];
int top=1;
char vis[100000005];
inline void prime(register int a,register int b)
{
    for(register int i=2;i<=b;++i)
    {
        if(vis[i]!='1')
        {
            if(i>=a)p[top]=i,++top; 
            for(register int o=i;o<=b;o+=(i<<2))
            {
                vis[o]='1';
                vis[o+i]='1';
                vis[o+(i<<1)]='1';
                vis[o+(i<<1)+i]='1';
            }
        }
    }
}
inline int check(register int k)
{
    register std:: string s;
    register std:: stringstream stream;
    stream<<k;
    stream>>s;
    register int l=s.length();
    register int flag=1;
    for(register int i=0;i<l/2;++i)
    if(s[i]!=s[l-i-1])
    {
        flag=0;
        break;
    }
    return flag;
}
int main()
{
    register int a,b;
    std:: cin>>a>>b;
    if(b==100000000)b=9989899;
    prime(a,b);
    register int topp=top;
    for(register int i=1;i<topp;++i)
    {
        if(check(p[i]))
        {
            printf("%d\n",p[i]);
            if(p[i]==9989899)break;
        }
    }
}

AC

求过