发现了一个神奇的现象，求大佬解惑

xdhking @ 2024-12-06 22:26:02

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

bool f[100000000] = { 1,1 };
int sum;
//质数筛
void Prime_() {
    for (unsigned long long i = 2; i < 100000000; i++) {
        if (f[i] == false) {
            for (unsigned long long j = i * i; j < 100000000; j += i) {
                f[j] = true;
            }
        }
    }
    return;
}
//求出位数
int Digit_(int n) {
    int cnt = 0;
    while (n) {
        n /= 10;
        cnt++;
    }
    return cnt;
}
//用来构造回文数，判断是否为质数，并输出，x为位数，y为递归的层数
void Function_(int& l, int& r, int x, int y) {
    if (x == 1) {//当只有一位数的情况，只有5,7满足
        for (int i = 5; i <= 7; i += 2) {
            if (i >= l && i <= r)
                cout << i << endl;
        }
        return;
    }
    else if (x == 2) {//当位数为2时只有11满足
        if (11 >= l && 11 <= r)
            cout << 11 << endl;
        return;
    }
    else if ((x & 1)== 0)//除了2，当位数为偶数时都不满足回文质数
        return;
    else {
        if (y > (x / 2) + 1) {//递归构造回文数
            if (f[sum] == false && sum <= r && sum >= l)
                cout << sum << endl;
            return;
        }
        else {
            int t = (x / 2) + 1;
            for (int i = 0; i <= 9; i++) {
                if (i == 0 && y == 1)//首位数字不能为0
                    continue;
                else {
                    if (y != t)//中间的数不需要加两次
                        sum += int(pow(10, t - y + 1) * i + pow(10, y - 1) * i);
                    else
                        sum +=int( pow(10, t - y + 1) * i);
                    Function_(l, r, x, y + 1);
                    if (y != t)
                        sum -= int(pow(10, t - y + 1) * i + pow(10, y - 1) * i);
                    else
                        sum -= int(pow(10, t - y + 1) * i);
                }
            }
        }
    }
    return;
}

int main() {
    int l, r, d1, d2;
    Prime_();
    cin >> l >> r;
    d1 = Digit_(l);//判断两端的位数
    d2 = Digit_(r);
    for (int i = d1; i <= d2; i++)//遍历能取到的所有位数
        Function_(l, r, i, 1);
    return 0;
}

by xdhking @ 2024-12-06 23:07:56

@Steve_xh 我去构造回文数加质数筛都能超时嘛，那我再优化一下，加一个判断如果遍历的回文数超出右范围了，就跳出递归，后面的回文数肯定是超出范围的

by xdhking @ 2024-12-06 23:12:48

@Terrible感谢大佬，学到了

by Steve_xh @ 2024-12-06 23:18:48

@xdhking

我尽力了。但是不知道为什么 WA 了（

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
int read(){
    int reans=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))reans=(reans<<1)+(reans<<3)+(ch^48),ch=getchar();
    return reans;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)return (void)putchar(x+48);
    write(x/10);
    putchar(x%10+48);
}
long long pow10[25];
bool f[100000000];
int sum;
//质数筛
void Prime_() {
    pow10[0]=1;
    for(int i=1;i<25;i++)
        pow10[i]=(pow10[i-1]<<1)+(pow10[i-1]<<3);
    f[0]=f[1]=1;
    for ( long long i = 2; i < 10000; i++) {
        if (f[i] == false) {
            for ( long long j = i * i; j < 100000000; j += i) {
                f[j] = true;
            }
        }
    }
    return;
}
//求出位数
int Digit_(int n) {
    int cnt = 0;
    while (n) {
        n /= 10;
        cnt++;
    }
    return cnt;
}
//用来构造回文数，判断是否为质数，并输出，x为位数，y为递归的层数
void Function_(int& l, int& r, int x, int y) {
    if (x == 1) {//当只有一位数的情况，只有5,7满足
        for (int i = 5; i <= 7; i += 2) {
            if (i >= l && i <= r)
                write(i),putchar('\n');
        }
        return;
    }
    else if (x == 2) {//当位数为2时只有11满足
        if (11 >= l && 11 <= r)
            puts("11");
        return;
    }
    else if ((x & 1)^1)//除了2，当位数为偶数时都不满足回文质数
        return;
    else {
        if (y > (x>>1) + 1) {//递归构造回文数
            if (f[sum] == false && sum <= r && sum >= l)
                write(sum),putchar('\n');
            return;
        }
        else {
            int t = (x >>1) + 1;
            for (int i = 0; i <= 9; i++) {
                if (i == 0 && y == 1)//首位数字不能为0
                    continue;
                else {
                    if (y != t)//中间的数不需要加两次
                        sum += pow10[t - y + 1] * i + pow10[y - 1] * i;
                    else
                        sum += pow10[t-y+1] * i;
                    Function_(l, r, x, y + 1);
                    if (y != t)
                        sum -= pow10[t-y+1] * i + pow10[y - 1]* i;
                    else
                        sum -= pow10[t-y+1] * i;
                }
            }
        }
    }
    return;
}
int l, r, d1, d2;

int main() {
    // cin.tie(nullptr)->sync_with_stdio(false);
    Prime_();
    l=read(),r=read();
    d1 = Digit_(l);//判断两端的位数
    d2 = Digit_(r);
    for (int i = d1; i <= d2; i++)//遍历能取到的所有位数
        Function_(l, r, i, 1);
    return 0;
}

https://www.luogu.com.cn/record/193195840

by Steve_xh @ 2024-12-06 23:21:02

主要优化是快读快写，10^n 预处理，还有质数筛的第一层循环可以只到 \sqrt n

by Steve_xh @ 2024-12-06 23:21:34

另有一堆（不知道是否有优化的）位运算

by xdhking @ 2024-12-06 23:30:02

@Steve_xh 大佬牛逼，快读快写这个东西我都没学过，我都准备把cin，cout换成scanf和printf了

.

by Steve_xh @ 2024-12-06 23:32:59

@xdhking

你可以试下把你说的那个边界优化也加上。另外你看下是不是原来的代码就 WA 了（

by xdhking @ 2024-12-06 23:41:21

@Steve_xh OK感谢大佬，我试试