素数回文（dfs，有bug）

时间：2023-07-09 16:08:32

素数回文

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 16487    Accepted Submission(s): 3677

Problem Description
xiaoou33对既是素数又是回文的数特别感兴趣。比如说151既是素数又是个回文。现在xiaoou333想要你帮助他找出某个范围内的素数回文数，请你写个程序找出 a 跟b 之间满足条件的数。(5 <= a < b <= 100,000,000);
Input
这里有许多组数据，每组包括两组数据a跟b。
Output
对每一组数据,按从小到大输出a，b之间所有满足条件的素数回文数（包括a跟b）每组数据之后空一行。
Sample Input
5 500
Sample Output
5 7 11 101 131 151 181 191 313 353 373 383

题解：好bug啊，题目上说包括a,b的，我怎么说一直wa，原来是因为我读清题了。。。我特判了b反到wa了。。。给一组5，7；题意应该是5，7；ac的确是5。。。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long LL;

const int MAXN = ;

int dp[MAXN];

int tp;

bool is_prime(int x){

    for(int i = ; i <= sqrt(x); i++){

        if(x % i == )return false;

    }

    return true;

}

void getx(int temp, int &x, int &y){

    int cur = ,cnt = , cur1 = ;

    x = temp, y = temp;

    while(temp){

        if(cnt)cur1 = cur1 *  + temp % , y *= ;

        cur = cur *  + temp % ;

        temp /= ;

        x *= ;

        cnt++;

    }

    x += cur;

    y += cur1;

}

void dfs(int cur, int cnt){

    if(cnt >= )return;

    int x, y;

    getx(cur, x, y);

//    printf("%d %d\n",x,y);

    if(is_prime(x))

        dp[tp++] = x;

    if(is_prime(y))

        dp[tp++] = y;

    for(int i = ; i <= ; i++){

        dfs(cur *  + i, cnt + );

    }

}

int main(){

    dp[] = ;

    dp[] = ;

    dp[] = ;

    dp[] = ;

    tp = ;

    dfs(,);

    dfs(,);

    dfs(,);

    dfs(,);

    sort(dp,dp + tp);

    int k = unique(dp,dp + tp) - dp;

    int a,b,x,y;

    //cout << dp[k] << " " << dp[k + 1] << endl;

    while(~scanf("%d%d",&a,&b)){

        x = lower_bound(dp, dp + k, a) - dp;

        y = lower_bound(dp, dp + k, b) - dp;

        //if(dp[y] > b)

        //    y--;

        for(int i = x; i < y; i++){

            printf("%d\n",dp[i]);

        }

        puts("");

    }

    return ;

}

相关文章