分析
-
考点:哈希表。
-
假设 $n = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2, (a \le b \le c \le d)$,则我们可以首先枚举
c, d
的值,将如果s = c * c + d * d
,让哈希表记录第一次和为s
对应的c、d
。 -
然后遍历
a、b
的值,当找到第一组符合要求的解就可以输出结果,然后结束程序即可。
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5000010;
int n;
int C[N], D[N]; // 哈希表, 存储 c^2+d^2 = s的话:C[s]=c, D[s]=d
int main() {
scanf("%d", &n);
memset(C, -1, sizeof C);
for (int c = 0; c * c <= n; c++)
for (int d = c; c * c + d * d <= n; d++) {
int s = c * c + d * d;
if (C[s] == -1) C[s] = c, D[s] = d;
}
for (int a = 0; a * a <= n; a++)
for (int b = 0; a * a + b * b <= n; b++) {
int s = n - a * a - b * b;
if (C[s] != -1) {
printf("%d %d %d %d\n", a, b, C[s], D[s]);
return 0;
}
}
return 0;
}