HNOI2002填数游戏

Question

P2232 [HNOI2002] 填数游戏

题目描述

某商店最近开展了一个答题有奖的促销活动，公司经理将若干道有一定难度的问题贴到了商场的宣传栏内，如果你能够做出其中一道的话，你就能够获得优惠购买商品的权利。一段日子以后，大多数题目都被消费者们找出了答案，可是惟独有一道题目难倒了所有的人，这道题目是这样描述的：

将不同的完全平方数填满 $n \times m$ 的矩形方格表中的每一个小方格，使得每行、每列的和也是完全平方数（这个和必须小于 ${10}^{17}$）。希望你找到一种合理的方案。

Tiger 希望自己能够获得优惠购物的权利，于是他找到了准备参加 NOI2002 的你，希望你能够帮他设计一个程序找到一种合理的方案。

输入格式

输入文件中仅有一行，为两个正整数 $n, m$（$2 \le n, m \le 15$）。

输出格式

如果有解的话，输出 $n$ 行，每行有 $m$ 个数，表示一种合理的填数方案，无解时输出 No answer。

输入输出样例 #1

输入 #1

2 2

输出 #1

225 1296
400 2304

Answer 1

这个链接，可以看下。

参考链接：

P2232 [HNOI2002] 填数游戏 题解 - 洛谷专栏 https://www.luogu.com.cn/article/avxe1prw

#include<cstdio>//P2232 [HNOI2002] 填数游戏

#define sqr(x) ((x)*(x))

using namespace std;

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() {
    // https://www.luogu.com.cn/article/avxe1prw
//    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("%lld",swap?sqr(r1[i]*r0[j]):sqr(r0[i]*r1[j]));
            printf((j+1==m)?"\n":" ");
        }
}