Help me!

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

Lin_Ziluo @ 2024-04-10 18:25:01

出了什么问题吗?

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <fstream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int a[15];
bool hwzs(int x){
    int ans1 = 0,ans2 = 0,ans = 0;
    for (int i = 2;i < x;i++) if (!(x % i)) return false; //刷掉合数。
    if (!(x / 10)) return true; //特判x为一位数的情况。 
    while (x){
        a[++ans] = x % 10;
        x /= 10;
    } //分离各位。 
    if (ans % 2){ //按位数的奇偶分开算。 
        for (int i = 1;i <= ans / 2 + 1;i++) ans1 += a[i] * pow(10,i - 1);
        for (int i = ans / 2 + 1;i <= ans;i++) ans2 += a[i] * pow(10,i - ans / 2 - 1); //如:a = {1,2,1},会分成12和21。  
    }else{
        for (int i = 1;i <= ans / 2;i++) ans1 += a[i] * pow(10,i - 1);
        for (int i = ans / 2 + 1;i <= ans;i++) ans2 += a[i] * pow(10,i - ans / 2 - 1); //如:a = {1,2,3,4},会分成12和34。 
    }                                                                           
    if (ans1 == ans2) return true;
    else return false; //判断是否是回文数。 
}
int main(){ //霉好的开始。 
    int a,b;
    cin >> a >> b; //输入a和b。 
    for (int i = a;i <= b;i++) if (hwzs(i)) cout << i << endl; //挨个判断是否是回文质数,是就输出。 
    return 0; //霉好的结束。 
}

by lunjiahao @ 2024-04-10 19:04:26

时间复杂度最坏为 O(n \sqrt n + n \ln n)n 最大可达 10^8,肯定会 TLE 啊


by lunjiahao @ 2024-04-10 19:07:24

@lpx0228

建议要么用欧拉筛要么优化枚举


by LJY_ljy @ 2024-04-10 19:22:53

@lpx0228 应该是枚举回文数的时候慢了,可以先按照回文数位数(留心一下 11 的倍数的特征)然后根据回文数位数来枚举每一位数,然后得到这个数来判断是否为质数(质数的判定也是有点小问题,到\ n^{1/2} \ 就可以判定\ n \ 是否为质数了)


by Lin_Ziluo @ 2024-04-10 19:38:59

@lunjiahao 我的问题不是TLE,是答案错了,它只输出一位数,往上不输出了。


by Lin_Ziluo @ 2024-04-10 19:41:40

@LJY_ljy 现在我不研究TLE的问题,我的问题是答案错了,WA懂吗?


by lunjiahao @ 2024-04-10 19:49:45

@lpx0228 为什么你的回文这样判


by lunjiahao @ 2024-04-10 19:51:09

@lpx0228

回文有问题


by lunjiahao @ 2024-04-10 19:51:47

@lpx0228 回文改成这样

for(int i=1,j=ans;i<j;i++,j--)
    if(a[i]^a[j]) return false;
return true; 

by Lin_Ziluo @ 2024-04-10 19:55:38

还能这样?!


by Lin_Ziluo @ 2024-04-10 19:56:04

三克油


| 下一页