为啥最后三个超时!!

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

shan_hai_wind @ 2024-10-11 10:29:44

#include <bits/stdc++.h>  
using namespace std; 

// 检查一个数是否为质数  
bool isPrime(int num) {  
    if (num == 2) return true; // 2 是质数  
    for (int i = 2; i <= sqrt(num); i++) {  
        if (num % i == 0) return false;  
    }  
    return true;  
}  

// 检查一个数是否为回文数  
bool isPalindrome(int num) {  
    int original = num;  
    int reversed = 0;  
    while (num) {  
        reversed = reversed * 10 + num % 10;  
        num /= 10;  
    }  
    return original == reversed;  
}  

int main() {  
    int a, b;
    scanf("%d %d",&a,&b);  
    if(a == 2) printf("2\n");
    if(a%2 == 0) a++;
    for (int i = a; i <= b; i=i+2) {  
        if (isPrime(i) && isPalindrome(i)) {  
            printf("%d\n",i);  
        }  
    }  
    return 0;  
}

by coding_goat @ 2024-10-11 10:34:24

@shan_hai_wind 兄弟,你光是循环从 110^8 都已经一秒了好吧www

然后就是你判断他是否是质数的时间复杂度是 O(\sqrt{n}) 的吧,那你时间复杂度不是 O(n\sqrt{n}) 的吗?过不了的啊!


by Melo_DDD @ 2024-10-11 10:43:14

@coding_goat 其实跑不到 10^810^8 也没有 1

@shan_hai_wind 但是楼上正解,\Theta(n\sqrt{n}) 确实会没


by shan_hai_wind @ 2024-10-11 10:49:46

可以过,我只要利用&&,先判断回文数就行了


by lihaoda @ 2024-10-11 10:51:08

@shan_hai_wind 怎么说一瞪眼肯定是O(n)的,n取了10^{8}


by shan_hai_wind @ 2024-10-11 10:52:04

@coding_goat 换一下&&两边函数,先判断回文会快很多,就可以过


by coding_goat @ 2024-10-11 10:58:15

@shan_hai_wind 是这样的,因为回文数个数少而且你循环跑不满 10^8,但是时间复杂度真的是 O(n\sqrt{n})


by coding_goat @ 2024-10-11 10:59:14

@coding_goat 如果想从时间复杂度上优化可以打表/学习 Miller-Rabin 素性测试


by shan_hai_wind @ 2024-10-11 11:49:25

@coding_goat 好的,谢谢你


|