自动搬运

查看原文

来自洛谷，原作者为

	一只小兔子 只会压行的蒟蒻

搬运于2025-08-24 21:35:25，当前版本为作者最后更新于2023-06-21 11:32:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一道简单却又不简单的简单题，为啥没有题解啊

题目大意：试找出一个 $n\times m$ 的元素由两两不同完全平方数构成的矩形表格，使得每行每列的和也为完全平方数（必须小于 $10^{17}$）。

考虑解构题目，为以下要求，逐个攻破：

• $n\times m$ 个完全平方数填入表格，每行每列的和也为完全平方数。

• 填入表格的数不能相等。

• 每行每列的和小于某上限。

无解情况和基础构造

对任意正整数 $n,m$，均有（无穷个）满足前两个条件的可行解。如果你能成功证明这个引理，恭喜你，你起步了。

证明：注意到，如果存在两数列满足其平方和为一完全平方数，即：

$$\sum^n_{i=1}a_i^2=A^2,\sum^m_{j=1}b_j^2=B^2$$

那么，以下构造为一个满足第一条件的 $n\times m$ 矩阵：

$$\begin{bmatrix} (a_1b_1)^2 & (a_1b_2)^2 & \ldots & (a_1b_m)^2\\ (a_2b_1)^2 & (a_2b_2)^2 & \ldots & (a_2b_m)^2\\ \vdots & \vdots & \ddots & \vdots\\ (a_nb_1)^2 & (a_nb_2)^2 & \ldots & (a_nb_m)^2\\ \end{bmatrix}$$

第 $i$ 行和第 $j$ 列的和为：

$$\sum^m_{j=1}(a_ib_j)^2=(a_iB)^2,\sum^n_{i=1}(a_ib_j)^2=(Ab_j)^2 $$

问题就变成找长度为 $n$ 的数列，使其平方和为完全平方。

根据小学二年级的恒等式有 $3^2+4^2=5^2$，那么考虑让前 $n-1$ 个数的平方和等于某数的三倍的平方，然后让最后一个为某数的四倍的平方，那么所有数的平方和为某数的五倍的平方，然后我们得到了这个：

$$3^{n-1},4\times 3^{n-2},5\times 4\times 3^{n-3},5^2\times 4\times 3^{n-4},...,5^{n-2}\times 4 $$

通项表达式是这个，请自行验证：

$$a_1=3^{n-1},a_i=5^{i-1}\times 4\times 3^{n-i}\quad(i>1) $$

受到启发，我们可以用任意勾股数 $A^2+B^2=C^2$ 构造：

$$a_1=A^{n-1},a_i=C^{i-1}\times B\times A^{n-i}\quad(i>1) $$

剩下的，就是说明，我们可以找到两个这样的数列，构造出上述矩阵，没有重复的平方数。除非数列中有两个数相同，否则重复的平方数不可能在同行或同列。两数平方相同，当且仅当，两者相差的质因子以各种方式被拉平，这是很好规避的，只要一方引入了特有的质因子，任意两数就会因为这个质因子的次数不同而不会相等。

举个例子，$3^2+4^2=5^2$ 作行数列和 $11^2+60^2=61^2$ 作列数列就可以做到，任意两数不同行会有质因子 $11^x$ 不同，同行不同列对应行数列位置也不同，杜绝了平方重复的可能。无限可能性来自于任何奇质数都存在于某勾股数中。证毕。

长整形限制和平方差

如果没有 $10^{17}$ 的括号的话，这就是个高精题，以上的构造完全没问题，当然 $5^{14}\times 4=24414062500>10^{10}$ 然后平方就炸了。

引用同样的记号，我们有：

$$\sum^{n-1}_{i=1}a_i^2=A^2-a_n^2=(A-a_n)(A+a_n)$$

不妨令 $A-a_n=k$，然后就有：

$$\sum^{n-1}_{i=1}a_i^2=ka_n+k^2$$

注意这里除最后一项前面全部自由，就是说你可以随便选择前面的数字，然后找到 $k$ 让 $a_n$ 满足以上条件就可以了。还是举个例子：

$$1^2+9^2+19^2+8^2+10^2=607=2\times 303+1$$ $$1^2+9^2+19^2+8^2+10^2+303^2=304^2$$

这里数字可以变得很小，上面 $n=6$ 的情况用勾股数构造的话，最后一项是 $(5^5\times 4)^2=12500^2$。

剩下的就是如何保证没有平方重复，方法就太多了。比如让行数列和列数列不共享任何质因子，或者直接质因子分解，或者搜索，或者奇奇怪怪的构造，等等。这是你的自由，请自己做主，这里不再赘述。注意，一定要判断最后一项是否也满足条件。

代码与验证程序

因为 SPJ 不完善，所以自己写了个验证程序。（抱歉，暂时不会写 SPJ，大佬可以随意更改）

\\verifier_2232.cpp
#include<iostream>
#include<fstream>
#include<cmath>
typedef long long ll;
const long long lim=1e17;// upper bound
bool issq(ll a){ll b=sqrt(a);return b*b==a;}
int main(int argc,char*argv[]){
	std::fstream inf("testdata.in");// <----- your answer from, change inf to cin if std::cin.
	std::fstream ouf("testdata.out");// <----- the judge result to, change ouf to cout if std::cout.
	int m,n;ll a[300];inf>>n>>m;// <----- requires n, m input, modify if needed.
	for(int i=0;i<n;i++)for(int j=0;j<m;j++){
		inf>>a[i*m+j];if(!issq(a[i*m+j])){
		ouf<<"Wrong answer! Detected non-square at ("<<i+1<<","<<j+1<<")!\n";return 0;}
	}
	for(int i=0;i<n*m;i++)for(int j=i+1;j<n*m;j++)if(a[i]==a[j]){
		ouf<<"Wrong answer! Detected repeated value: "<<a[i]<<"!\n";return 0;
	}
	for(int i=0;i<n;i++){ll lsum=0;
		for(int j=0;j<m;j++)lsum+=a[i*m+j];if(!issq(lsum)||lsum>=lim){
		ouf<<"Wrong answer! Row "<<i+1<<" sums to non-square or is too large!\n";return 0;}
	}
	for(int j=0;j<m;j++){ll csum=0;
		for(int i=0;i<n;i++)csum+=a[i*m+j];if(!issq(csum)||csum>=lim){
		ouf<<"Wrong answer! Column "<<j+1<<" sums to non-square or is too large!\n";return 0;}
	}
	ouf<<"Answer correct!\n";
}

代码正文

#include<cstdio>//P2232 [HNOI2002] 填数游戏
#define sqr(x) ((x)*(x))
const int N=22+32;
long long r0[N],r1[N];
int primes[N]={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,
59,61,67,71,73,79,83,89,97,101,103,107,109,113,127};
void manage(int n,int m){
	for(int i=0;i<n;++i)r0[i]=primes[i];if(n%2==0)r0[0]<<=1;
	for(int i=0;i<m;++i)r1[i]=primes[i+n];if(m%2==0)r1[0]<<=1;
}
void generate(long long* rw,int n,long long tmp=0){
	for(int i=0;i<n;++i)tmp+=sqr(rw[i]);rw[n]=(tmp-1)/2;
	for(int j=3;j<100;j+=2)if((tmp/j>rw[n-1]*2+j)&&(tmp-j*j)%(2*j)==0)rw[n]=(tmp-j*j)/2/j;
}
int main(){
//	freopen("testdata.in","w",stdout);printf("%d %d\n",n,m);
	int n,m;scanf("%d%d",&n,&m);
//	int swap=0;if(n<m)n^=m^=n^=m,swap=1;if(n==11&&m==6)swap^=1,n^=m^=n^=m;
	manage(n-1,m-1);generate(r0,n-1);generate(r1,m-1);//if(swap)n^=m^=n^=m;
	for(int i=0;i<n;++i)for(int j=0;j<m;++j)
	{printf("%lld",swap?sqr(r1[i]*r0[j]):sqr(r0[i]*r1[j]));printf((j+1==m)?"\n":" ");}
}