题意简介

要求构造一个由不大于 1e5 的非负数构成的正方形矩阵，矩阵的每个元素不是质数，但每一行、每一列的数字的和都是质数。

思路分析

看到样例二，我们知道数字可以重复。

于是，我们很容易推出，如果 n 是个质数，那直接输出 n*n 个 1 就行了。

那么假如 n 不是质数呢？

我们很容易想到，如果存在某个非质数的非负数 x 使得 (n-1)*1+x 是个质数的话，那么只需要把这个 x 安在其中一条对角线上、其余位置全部放 1 就完事了。

于是打个暴力验证一下，发现这个 x 是必定存在的。

所以直接预处理出每个 n 对应的 x，然后读入的时候输出对应的矩阵就行了。

代码库

验证

#include <cstdio>

#include <cstring>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define Rep(i,a,b) for(int i=a;i>=b;i--)

const int M=2e5,N=2e4+5;

bool vis[M+5]; int prim[N],cc;

int main(){

    vis[0]=vis[1]=1;

    rep(i,2,M){

        if(!vis[i]) prim[++cc]=i;

        rep(j,1,cc){

            if(prim[j]*i>M) break;

            vis[prim[j]*i]=1;

            if(i%prim[j]==0) break;

        }

    }

    bool f[101]; memset(f,0,sizeof(f));

    rep(i,2,100){

        Rep(j,cc,1){

            if(prim[j]<(i-1)) break;

            if(prim[j]-(i-1)>(M>>1)) continue;

            if(vis[prim[j]-(i-1)]){ f[i]=1; break; }

        }

    }

    rep(i,2,100) if(!f[i]) f[0]=1,printf("Err in %d\n",i);

    if(!f[0]) printf("Nice!\n");

    return 0;

}

题解

#include <cstdio>

#include <cstring>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define Rep(i,a,b) for(int i=a;i>=b;i--)

const int M=2e5,N=2e4+5;

bool vis[M+5]; int prim[N],cc,t,n,f[101];

void pre_work(){

	vis[0]=vis[1]=1;

    rep(i,2,M){

        if(!vis[i]) prim[++cc]=i;

        rep(j,1,cc){

            if(prim[j]*i>M) break;

            vis[prim[j]*i]=1;

            if(i%prim[j]==0) break;

        }

    }

    rep(i,2,100){

        Rep(j,cc,1){

            if(prim[j]<(i-1)) break;

            if(prim[j]-(i-1)>(M>>1)) continue;

            if(vis[prim[j]-(i-1)]){ f[i]=prim[j]-(i-1); break; }

        }

    }

}

int main(){

    pre_work(); scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        rep(i,1,n){

            rep(j,1,n){

                if(i==j) printf("%d ",f[n]);

                else printf("1 ");

            }

            putchar('\n');

        }

    }

    return 0;

}

巴特西

【CF1436B】Prime Square 题解

题意简介

思路分析

代码库

验证

题解

END

最新文章

热门文章