超时,炸裂!!!!1

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

Miracle_InDream @ 2024-10-23 22:33:25

自己对着今天的 3 个帖子调了半天还超时,不吸氧超时,吸氧能过,但是我不服(((

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    for(int i=a;i<=b;i++)
    {
        int c=i;
        int d=0;
        while(c>0)
        {
            d*=10;
            d+=c%10;
            c/=10;
        }
        if(d==i)
        {
            bool flag=1;
            if(i==1)
            {
                continue;
            }
            if(i==2)
            {
                printf("%d\n",i);
                continue;
            }
            if(i%2==0)
            {
                continue;
            }
            for(int j=3;j*j<=i;j++)
            {
                if(i%j==0)
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                printf("%d\n",i);
            }
        }
    }
    return 0;
}

by _Never_Die_ @ 2024-10-23 22:37:24

没有偶数位的回文质数,b取min(9989899,b)即可


by Eric998 @ 2024-10-23 22:40:48

@Miracle_InDream 这东西是常数不大的O(n\log n),过不了1e8很正常qwq

不吸氧要过先枚举长度,再跑出所有回文数,可以做到O(N)。亚线性应该不可做(?)


by Eric998 @ 2024-10-23 22:44:17

@_NeverDie 是的,我想唐了,偶数为回文数是11的倍数。


|