这里面会放一些我做过的非乱搞的好题，乱搞请出门右转乱搞记录。
CF417E Square Table
考虑先构造一行，设为 $a$。
当 $n=1$ 时，直接扔个平方数上去就是合法的。
当 $n=2$ 时，令 $a=[3,4]$ 即可。
否则，当 $n$ 是奇数的时候，令 $a$ 第一项为 $2$，然后 $n-2$ 项为 $1$，最后一项是 $\frac{n+1}{2}$ 即可满足要求。
当 $n$ 是偶数的时候，令 $a$ 前 $n-1$ 项为 $1$，最后一项为 $\frac{n}{2}-1$ 即可。
证明：当 $n$ 是奇数的时候，该行的和为：$(\frac{n+1}{2})^2+n+2=(\frac{n}{2}+1)^2$。
当 $n$ 是偶数的时候，该列的和为：$(\frac{n}{2}-1)^2+n-1=(\frac{n}{2})^2$。
列的构造方式同理，设为 $b$。
再考虑拓展到 $n\times m$ 的矩阵上，事实上，令 $c[i][j]=a[i]\times b[j]$ 就是符合要求的。
证明：矩阵 $c$ 第 $i$ 行的平方和为：$a[i]^2\times \sum_{j=1}^n{b[j]^2}$。因为 $b$ 的平方和是一个平方数，所以 $c$ 每一行的平方和也是平方数。列的证明方式同理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005],lc[1005],rc[1005];
int main(){
cin>>n>>m;
if(n==1){
if(m==1){cout<<"1\n";return 0;}
if(m==2){cout<<"3 4\n";return 0;}
if(m&1^1){
for(int i=1;i<m;++i)cout<<"1 ";
cout<<(m-2)/2<<'\n';return 0;
}
else{
cout<<"2 ";
for(int i=2;i<m;++i)cout<<"1 ";
cout<<((m+1)/2)<<'\n';return 0;
}
}
if(m==1){
if(n==2){cout<<"3\n4\n";return 0;}
if(n&1^1){
for(int i=1;i<n;++i)cout<<"1\n";
cout<<(n-2)/2<<'\n';return 0;
}
else{
cout<<"2\n";
for(int i=2;i<n;++i)cout<<"1\n";
cout<<((n+1)/2)<<'\n';return 0;
}
}
if(n==2){lc[1]=3;lc[2]=4;}
else if(n&1^1){
for(int i=1;i<n;++i)lc[i]=1;
lc[n]=(n-2)/2;
}
else{
lc[1]=2;
for(int i=2;i<n;++i)lc[i]=1;
lc[n]=((n+1)/2);
}
if(m==2){rc[1]=3;rc[2]=4;}
else if(m&1^1){
for(int i=1;i<m;++i)rc[i]=1;
rc[m]=(m-2)/2;
}
else{
rc[1]=2;
for(int i=2;i<m;++i)rc[i]=1;
rc[m]=((m+1)/2);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)a[i][j]=lc[i]*rc[j];
for(int i=1;i<=n;++i,cout<<'\n')
for(int j=1;j<=m;++j)cout<<a[i][j]<<' ';
cout<<'\n';
return 0;
}
|
