题解 CF1436B 【Prime Square】

题目大意

构造一个 (n*n) 的矩阵,满足里面每个数都不为质数,但每行每列之和为质数．

solution

刚拿到题被吓到了一下，以为要写爆搜，然后判断是不是满足条件．

但是这是Ｂ题，一定还有更快的方法，

注意到，

all numbers on the square are non-negative integers not exceeding (10^5);

只要非负？那么 (0) 也可以了。

一下子简单了，我们只要这样构造：

1 1 0 0 0
0 1 1 0 0
0 0 1 1 0
0 0 0 1 1
1 0 0 0 1

也就是当 (i = j) 或者 (i = j+1) 或者 (i = n,j = 1)时 (a[i][j]) 为(1)，其他为 (0)。

1,0 都不是质数，但每行每列之和为 (2) ，是质数。

于是就水完了这道题。

代码

快读、头文件自行脑补

int n;
int main (){
	int T; read(T);
	while(T--){
		read(n);
		for(int i = 1;i <= n;i++){
		    for(int j = 1;j <= n;j++)
			if(j == i+1||j == i||(j == 1&&i==n)) printf("1 ");
			else printf("0 ");
		    puts("");
		}
		printf("
");
	}
	return 0;
}