《为何各位大佬的方法如此简洁》

前导：《一篇转专为新手写的TJ》

先来新手最爱的环节AC code：(正文在code下方)

没登录和想抄tj的别走，在最下面有code（无注释）

注：抄题解有害rp，请慎思笃行

结论：ans=989457

#include<bits/stdc++.h>
#include<omp.h>
#define int long long
using namespace std;
//定义最大范围常量，1e6+10
const int maxn = 1e6 + 10;
//记是否为质数的数组
bool is_prime[maxn];
//存储所有质数的数组
int primes[maxn];
//质数计数器
int pcnt;
//X质数计数器
int cnt;
//线性筛法生成质数表
void linear_sieve(){
    //初始化is_prime数组，全部设为true
    memset(is_prime,true,sizeof(is_prime));
    //0和1不是质数
    is_prime[0]=is_prime[1]=false;
    //从2开始遍历到maxn-5
    for(int i=2;i<=maxn-5;i++){
        //如果i是质数，加入primes数组
        if(is_prime[i])primes[++pcnt] = i;
        //筛去i与已知质数的乘积
        for(int j=1;j<= pcnt && i*primes[j]<=maxn-5;j++){
            //标记i*primes[j]为非质数
            is_prime[i*primes[j]]=false;
            //如果i能被primes[j]整除，跳出循环
            if(i%primes[j]==0)break;
        }
    }
}
//检查数字num是否为X质数
bool check(int num){
    //存储数字的各位数字
    int digits[10];
    //数字的位数
    int len=0;
    //临时变量用于分解数字
    int temp=num;
    //分解数字的各位数字
    while(temp){
        digits[len++]=temp % 10;
        temp/=10;
    }
    //反转数组，保持原始顺序
    reverse(digits,digits+len);
    //使用数位DP生成所有子序列
    for(int mask=1;mask<(1<<len);mask++){
        //候选数字
        int candidate=0;
        //标记是否处理前导零
        bool leading_zero=true;
        //遍历每一位
        for(int i=0; i<len;i++){
            //检查该位是否在子序列中
            if(mask & (1<<i)){
                //跳过前导零
                if(leading_zero && digits[i]==0)break;
                leading_zero=false;
                //构建候选数字
                candidate=candidate*10+digits[i];
            }
        }//检查候选数字是否为质数
        if(!leading_zero && candidate<=maxn-5 && is_prime[candidate])
            return true;
    }
    return false;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//仪式感 
    //生成质数表
    linear_sieve();
    //使用OpenMP并行计算
    //#pragma omp parallel for：并行化for循环
    //reduction(+:cnt)：对cnt进行求和归约
    #pragma omp parallel for reduction(+:cnt)
    //遍历
    for(int num=1;num<=1e6;num++) {
        //检查是否为X质数
        if(check(num))cnt++;
    }
    cout<<cnt<<'\n';//完结撒花 
    return 0;
}

正文

题目重述

对于一个含有 M 个数位的正整数 N，任意选中其中 K 个不同的数位（0≤K<M），将这些选中的数位删除之后，余下的数位按照原来的顺序组成了一个新的数字 P。如果至少存在一个 P 是质数，我们就称 N 是一个 X 质数。例如，7869 删除 7 和 6 得到 89，89 是质数，所以 7869 是 X 质数。77 删除一个 7 得到 7，也是质数，所以 77 是 X 质数。求 1 到 1,000,000 中有多少个 X 质数。

代码思路

核心：由于O小姐今天开心（之前可不是这样的T-T），所以O(...)并不高，直接暴力枚举

①预处理所有可能子序列
②写判断函数
③直接枚举

代码实现

①线性筛预处理，方便操作
②数位DP生成，同时顺便判断
③直接无脑枚举

具体见代码，每行都有注释，十分详细

完结撒花

代码提交结果：
传送门

后记：这个code装[数据删除]一分钟，纠错一坤年

#include<bits/stdc++.h>
#include<omp.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
bool is_prime[maxn];
int primes[maxn];
int pcnt;
int cnt;
void linear_sieve(){
    memset(is_prime,true,sizeof(is_prime));
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=maxn-5;i++){
        if(is_prime[i])primes[++pcnt] = i;
        for(int j=1;j<= pcnt && i*primes[j]<=maxn-5;j++){
            is_prime[i*primes[j]]=false;
            if(i%primes[j]==0)break;
        }
    }
}
bool check(int num){
    int digits[10];
    int len=0;
    int temp=num;
    while(temp){
        digits[len++]=temp % 10;
        temp/=10;
    }
    reverse(digits,digits+len);
    for(int mask=1;mask<(1<<len);mask++){
        int candidate=0;
        bool leading_zero=true;
        for(int i=0; i<len;i++){
            if(mask & (1<<i)){
                if(leading_zero && digits[i]==0)break;
                leading_zero=false;
                candidate=candidate*10+digits[i];
            }
        }
        if(!leading_zero && candidate<=maxn-5 && is_prime[candidate])
            return true;
    }
    return false;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    linear_sieve();
    #pragma omp parallel for reduction(+:cnt)
    for(int num=1;num<=1e6;num++){
        if(check(num))cnt++;
    }
    cout<<cnt<<'\n';
    return 0;
}

#include<bits/stdc++.h>
#include<omp.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
bool is_prime[maxn];
int primes[maxn];
int pcnt;
int cnt;
void linear_sieve(){
    memset(is_prime,true,sizeof(is_prime));
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=maxn-5;i++){
        if(is_prime[i])primes[++pcnt] = i;
        for(int j=1;j<= pcnt && i*primes[j]<=maxn-5;j++){
            is_prime[i*primes[j]]=false;
            if(i%primes[j]==0)break;
        }
    }
}
bool check(int num){
    int digits[10];
    int len=0;
    int temp=num;
    while(temp){
        digits[len++]=temp % 10;
        temp/=10;
    }
    reverse(digits,digits+len);
    for(int mask=1;mask<(1<<len);mask++){
        int candidate=0;
        bool leading_zero=true;
        for(int i=0; i<len;i++){
            if(mask & (1<<i)){
                if(leading_zero && digits[i]==0)break;
                leading_zero=false;
                candidate=candidate*10+digits[i];
            }
        }
        if(!leading_zero && candidate<=maxn-5 && is_prime[candidate])
            return true;
    }
    return false;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    linear_sieve();
    #pragma omp parallel for reduction(+:cnt)
    for(int num=1;num<=1e6;num++){
        if(check(num))cnt++;
    }
    cout<<cnt<<'\n';
    return 0;
}