CF417E Square Table 做题记录

给你一个 $N\times M$ 的矩阵，要求在每一个格子内填一个不超过 $10^8$ 的正整数，使得每一行和每一列的数的平方和仍然是一个平方数。

$1\le n,m\le 100$。

降至了，构造矩阵等价于构造一行 $a_i$ 和一列 $b_i$，每个格子 $(i,j)$ 为 $a_ib_j$。

那么行列可以分开构造，并且行列等价，所以问题转化为了构造长度为 $n$ 的整数数组 $a_i$ 满足 $1\le a_i\le 10^4$ 且 $\sum a_i^2$ 是平方数。

这很简单，只需要构造

$\{4,4,4,4,\dots,4n-5\}$

即可，代码如下：

// Problem: Square Table
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF417E
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005;

int n,m;
int a[S],b[S];

inline void slove(int n,int a[])
{
	if(n==1) return a[1]=1,void();
	for(int i=1;i<=n-1;i++) a[i]=4;
	a[n]=4*n-5;
}

int main()
{
	scanf("%d%d",&n,&m);
	slove(n,a),slove(m,b);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) printf("%d ",a[i]*b[j]);
		printf("\n");
	}
	return 0;
}