【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