P2232 [HNOI2002] 填数游戏 题解

· · 题解

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

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

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

无解情况和基础构造

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

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

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

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

(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":" ");}
}