1 solutions

  • 1
    @ 2023-9-21 16:34:11

    爆搜,调炸了,三天才过。

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    ll a[6][6],k;
    bool vis[100000];
    bool flag=true;
    priority_queue<string,vector<string>,greater<string> > ans;
    void print();
    void dfs8(){
        a[4][5]=k-a[4][1]-a[4][2]-a[4][3]-a[4][4];
        if(a[4][5]>=0&&a[4][5]<=9){
            if(vis[a[4][1]*10000+a[4][2]*1000+a[4][3]*100+a[4][4]*10+a[4][5]]){
                a[5][4]=k-a[5][1]-a[5][2]-a[5][3]-a[5][5];
                if(a[5][4]>=0&&a[5][4]<=9){
                    if(vis[a[5][1]*10000+a[5][2]*1000+a[5][3]*100+a[5][4]*10+a[5][5]]){
                        a[3][4]=k-a[1][4]-a[2][4]-a[4][4]-a[5][4];
                        if(a[3][4]>=0&&a[3][4]<=9){
                            if(vis[a[1][4]*10000+a[2][4]*1000+a[3][4]*100+a[4][4]*10+a[5][4]]){
                                ll t1=k-a[3][1]-a[3][2]-a[3][3]-a[3][4],t2=k-a[1][5]-a[2][5]-a[4][5]-a[5][5];
                                if(t1==t2&&t1>=0&&t2<=9){
                                    a[3][5]=t1;
                                    if(vis[a[1][5]*10000+a[2][5]*1000+a[3][5]*100+a[4][5]*10+a[5][5]]){
                                        if(vis[a[3][1]*10000+a[3][2]*1000+a[3][3]*100+a[3][4]*10+a[3][5]]){
                                            print();
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    void dfs7(){
        for(ll i=0;i<=k-a[1][3]-a[2][3]-a[3][3]&&i<=9;i++){
            a[4][3]=i;
            a[5][3]=k-a[1][3]-a[2][3]-a[3][3]-a[4][3];
            if(a[5][3]>9) continue;
            if(vis[a[1][3]*10000+a[2][3]*1000+a[3][3]*100+a[4][3]*10+a[5][3]]) dfs8();
        }
    }
    void dfs6(){
        for(ll i=0;i<=k-a[1][2]-a[2][2]-a[4][2]&&i<=9;i++){
            a[3][2]=i;
            a[5][2]=k-a[1][2]-a[2][2]-a[3][2]-a[4][2];
            if(a[5][2]>9)  continue;
            if(vis[a[1][2]*10000+a[2][2]*1000+a[3][2]*100+a[4][2]*10+a[5][2]]) dfs7();
        }
    }
    void dfs5(){
        for(ll i=0;i<=k-a[2][1]-a[2][2]-a[2][4]&&i<=9;i++){
            a[2][3]=i;
            a[2][5]=k-a[2][1]-a[2][2]-a[2][3]-a[2][4];
            if(a[2][5]>9) continue;
            if(vis[a[2][1]*10000+a[2][2]*1000+a[2][3]*100+a[2][4]*10+a[2][5]]) dfs6();
        }
    }
    void dfs4(){
        for(ll i=0;i<=k-a[5][1]-a[3][3]-a[1][5]&&i<=9;i++){
            a[4][2]=i;
            a[2][4]=k-a[5][1]-a[4][2]-a[3][3]-a[1][5];
            if(a[2][4]>9) continue;
            if(vis[a[5][1]*10000+a[4][2]*1000+a[3][3]*100+a[2][4]*10+a[1][5]]) dfs5();
        }
    }
    void dfs3(){
        for(ll i=1;i<=k-a[1][1]&&i<=9;i++){
            a[2][1]=i;
            for(ll j=1;j<=k-a[1][1]-a[2][1]&&j<=9;j++){
                a[3][1]=j;
                for(ll kk=1;kk<=k-a[1][1]-a[2][1]-a[3][1]&&kk<=9;kk++){
                    a[4][1]=kk;
                    a[5][1]=k-a[1][1]-a[2][1]-a[3][1]-a[4][1];
                    if(a[5][1]>9) continue;
                    if(vis[a[1][1]*10000+a[2][1]*1000+a[3][1]*100+a[4][1]*10+a[5][1]]){
                        dfs4();
                    }
                }
            }
        }
    }
    void dfs2(){
        for(ll i=1;i<=k-a[1][1]&&i<=9;i++){
            a[1][2]=i;
            for(ll j=1;j<=k-a[1][1]-a[1][2]&&j<=9;j++){
                a[1][3]=j;
                for(ll kk=1;kk<=k-a[1][1]-a[1][2]-a[1][3]&&kk<=9;kk++){
                    a[1][4]=kk;
                    a[1][5]=k-a[1][1]-a[1][2]-a[1][3]-a[1][4];
                    if(a[1][5]>9) continue;
                    if(vis[a[1][1]*10000+a[1][2]*1000+a[1][3]*100+a[1][4]*10+a[1][5]]){
                        dfs3();
                    }
                }
            }
        }
    }
    void dfs1(){
        for(ll i=0;i<=k-a[1][1]&&i<=9;i++){
            a[2][2]=i;
            for(ll j=0;j<=k-a[1][1]-a[2][2]&&j<=9;j++){
                a[3][3]=j;
                for(ll kk=0;kk<=k-a[1][1]-a[2][2]-a[3][3]&&kk<=9;kk++){
                    a[4][4]=kk;
                    a[5][5]=k-a[1][1]-a[2][2]-a[3][3]-a[4][4];
                    if(a[5][5]>9) continue;
                    if(vis[a[1][1]*10000+a[2][2]*1000+a[3][3]*100+a[4][4]*10+a[5][5]]){
                        dfs2();
                    }
                }
            }
        }
    }
    int main(){
        for(ll i=2;i<=99999;i++) vis[i]=true;
        for(ll i=2;i<=99999;i++) if(vis[i]) for(ll j=i;j*i<=99999;j++) vis[i*j]=false;
        scanf("%lld %lld",&k,&a[1][1]);
        if(a[1][1]==0){
            printf("NONE");
            return 0;
        }
        dfs1();
        if(flag) printf("NONE");
        else{
        	while(!ans.empty()){
        		for(ll i=1;i<=5;i++){
        			for(ll j=1;j<=5;j++) printf("%c",ans.top()[(i-1)*5+(j-1)]);
        			printf("\n");
    			}
    			printf("\n");
    			ans.pop();
    		}
    	}
        return 0;
    }
    void print(){
    	string s="";
        flag=false;
        for(ll i=1;i<=5;i++) for(ll j=1;j<=5;j++) s=s+char(a[i][j]+'0');
        ans.push(s);
    }
    
    • 1

    Information

    ID
    26
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    9
    Tags
    # Submissions
    16
    Accepted
    2
    Uploaded By