【CF1436B】Prime Square 题解

• 2020 年 10 月 25 日
• 筆記
• Codeforces, 题解

原题链接

题意简介

要求构造一个由不大于 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;
}

END