题解：B4158 [BCSP-X 2024 12 月小学高年级组] 质数补全

· · 题解

考场上睡着了，只水过了这一道题。

质数补全 题解

我的考场代码太过于难看，所以其实这是一篇全新出炉的题解。

题目大意

有一些质数，但是质数的某些数位不告诉你，请你判断这能否是一个质数。如果是，输出最小的可能，否则输出 -1。

题目解法

大多人想到了搜索解法，但我的想法与众不同。我们先来说一下为什么能用搜索，原因很简单就是 n \le 7 的数据范围太过于小，导致七重循环都可以过。这里我提到了“七重循环”，没错我就是这么“七重循环”写的。

具体写法

我写的数组很多，所以可能会有点绕。

首先定义一个 vis 数组来判断第 i 个数是否确定，接着定义两个数组 st 与 en，代表第 i 个数位的范围。注意，如果这个数位为固定的那就是那个数，否则范围是 0\sim9。

用字符串来存储整个数，接着完成上述内容，最后七重循环，看组合出来的数是否为质数，如果是的话直接输出即可。而如果循环后，没有任意一个数满足要求，输出 -1。

AC code

#include <bits/stdc++.h>
using namespace std;
char a[10];
int vis[10];
int st[10],en[10];
bool is_prime(int x){ // 判断质数
    if(x==0||x==1) return false;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        // 初始化
        memset(vis,0,sizeof vis);
        memset(st,0,sizeof st);
        memset(en,0,sizeof en);
        cin>>a;
        int len=strlen(a);
        int sum=0;
        for(int i=0;i<len;i++){
            if(a[i]=='*'){
                vis[i]=1;
                sum++;
            }
        }
        for(int i=0;i<len;i++){
            if(vis[i]==0){ // 如果是固定的，那么循环时直接固定数
                st[7-len+i]=a[i]-'0';
                en[7-len+i]=st[7-len+i];
            }else{ // 否则将所有数全部循环一遍
                st[7-len+i]=0;
                en[7-len+i]=9;
            }
        }
        bool flag=0; // 判断是否有数满足条件
        // 开始循环
        for(int i1=st[0];i1<=en[0];i1++){
            for(int i2=st[1];i2<=en[1];i2++){
                for(int i3=st[2];i3<=en[2];i3++){
                    for(int i4=st[3];i4<=en[3];i4++){
                        for(int i5=st[4];i5<=en[4];i5++){
                            for(int i6=st[5];i6<=en[5];i6++){
                                for(int i7=st[6];i7<=en[6];i7++){
                                    if(is_prime(i1*1000000+i2*100000+i3*10000+i4*1000+i5*100+i6*10+i7)&&flag==0){
                                        cout<<i1*1000000+i2*100000+i3*10000+i4*1000+i5*100+i6*10+i7;
                                        flag=1;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(flag==0){
            cout<<-1;
        }
        cout<<endl;
    }
    return 0; // 好习惯
}