求助求助,急需大佬帮助

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

chengkelin2024 @ 2024-06-14 13:00:09

#include<bits/stdc++.h>
using namespace std;
int main(){
    int sum=1000;
    int d1,d2,d3,a,b;
    cin>>a>>b;
    int i = 0;
    int palindrome[10000];
    for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome[0+i] = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
           i++;
           sum++;
         }
     }
 }
    cin>>a>>b;
    for(int i=1;i<=sum;i++){
    if(palindrome[i]>=a&&palindrome[i]<=b){
    cout<<palindrome[i];
    }
}
    return 0;
}

哪里错了谢谢


by lxc129 @ 2024-06-23 18:42:53

你也可以用另外一种思路做一下:@chengkelin
把所有奇数全部判一遍,当奇数位数是2/4/6且此数不是11时,直接跳到3/5/7位枚举就行。
证明:

2$位:原数${\overline{xx}}=11x(x≠1)$ ,易得知$11{\mid}11x 4$位:原数${\overline{xyyx}}=1001x+110y$,易得知$11{\mid}1001x+110y $O({\sqrt{n}})$的质数筛上面都有了就不写了。 核心代码: ```cpp if (l%2==0) l++; for (int i=l;i<=r;i+=2){ int len=0,x=i; while (x){ x/=10; len++; } if (len==4) i=10301; if (len==6) i=1003001; if (!checkhui(i)) continue; if (ip(i)) cout<<i<<'\n'; } ``` 判断顺序: $1.$先判断是否为$2/4/6$位数($2$位数的我懒得写了),复杂度$O(log_{10}^{x}) 2.$判断是否为回文数$O(log_{10}^{x}) 3.$判断是否为质数$O(\sqrt{n})

上一页 |