Codeforces 417E Square Table(随机算法)

题目链接：Codeforces 417E Square Table

题目大意：给出n和m，要求给出一个矩阵，要求每一列每一行的元素的平方总和是一个平方数。

解题思路：构造，按照

a a a b

a a a b

a a a b

c c c d

的方式取构造，然后a，b，c，d的值用随机生成数去枚举，不过我觉得用暴力也是可以的。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>

bool judge (int s) {
	int k = sqrt(s);
	return k * k == s;
}

int main () {
	int n, m;
	int a, b, c, d;

	scanf("%d%d", &n, &m);

	while (true) {
		a = rand()%100 + 1;
		b = rand()%100 + 1;
		c = rand()%100 + 1;
		d = rand()%100 + 1;

		if (judge(a * a * (m-1) + b * b)
		 && judge(a * a * (n-1) + c * c)
		 && judge(b * b * (n-1) + d * d)
		 && judge(c * c * (m-1) + d * d) )
			break;
	}

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++)
			printf("%d ", a);
		printf("%d\n", b);
	}

	for (int i = 1; i < m; i++)
			printf("%d ", c);
	printf("%d\n", d);
	return 0;
}