问题描述
这道题时间复杂度大概只能枚举两个数，所以我们可以用空间换时间。
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
5=02+02+12+22
7=12+12+12+22
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。
输入格式
输入一个正整数 N。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
0<N<5∗106
输入样例：
5
输出样例：
0 0 1 2
思路
这里介绍效率最高的枚举加哈希解法，其余解法代码下面会一起给出。
由于暴力枚举法复杂度过高，需要枚举三个数值，所以我们可以优化一下，用空间换时间，先把前两个数的平方和用数组存起来。比如现在枚举到两个数 i 和 j，计算平方和后为 i*i+j*j，于是我们可以用一个数组 h 来将结果存起来，即 h[i*i+j*j]=i+1，这里只用标记 i 就好了，j 可以通过 n 来反推出来，这就节省了空间。
**注意：**这里之所以存的是 i+1 而不是 i，是因为数组 h 初始化为 0，所以用 i+1 防止 i=0 时在后面判断查找跳过 i=0 的情况。
接着再去枚举后两个数，假设是 c 和 d，那么 a 和 b 的平方和 t 就可以通过用 n 减去 a 和 b 的平方和得到。然后再判断这个平方和 t 是否在哈希表即数组 h 中存在，如果存在则将 a 和 b 反推出来，最终打印结果即可。
代码
暴力法
这种方法时间复杂度很高，但是暴力杯还是能过的。
#include <bits/stdc++.h> using namespace std; int n; int main() { cin >> n; for (int a = 0; a * a <= n; a++) for (int b = a; a * a * a + b * b <= n; b++) for (int c = b; a * a + b * b + c * c <= n; c++) { int t = n - a * a - b * b - c * c; int d = sqrt(t); if (d * d == t) { cout << a << " " << b << " " << c << " " << d << endl; return 0; } } }
二分法
#include <bits/stdc++.h> using namespace std; int n, m = 0; const int N = 2500010; struct Sum { int s, c, d; bool operator < (const Sum &t)const { if (t.s != s) return s < t.s; if (t.c != c) return c < t.c; return d < t.d; } } sum[N]; int main() { cin >> n; for (int c = 0; c * c <= n; c++) for (int d = c; c * c + d * d <= n; d++) sum[m++] = {c *c + d * d, c, d}; sort(sum, sum + m); for (int a = 0; a * a <= n; a++) for (int b = a; a * a + b * b <= n; b++) { int t = n - a * a - b * b; int l = 0, r = m - 1; while (l < r) { int mid = l + r >> 1; if (sum[mid].s >= t) r = mid; else l = mid + 1; } if (sum[r].s == t) { cout << a << " " << b << " " << sum[r].c << " " << sum[r].d << endl; return 0; } } }
枚举+哈希
#include <iostream> #include <cmath> using namespace std; const int N = 1e8 + 10; int h[N]; int main() { int n; cin >> n; //打表，找出1 - n，所有完全平方数两两之和，如果存在只记第一次出现（题目要求找出字典序小的） for (int i = 0; i * i * 2 <= n; i++) { for (int j = i; j * j + i * i <= n; j++) { if (!h[i * i + j * j]) h[i * i + j * j] = i + 1;//防止i = 0时在后面判断查找跳过 i = 0的情况 } } //0<= a <= b <= c <= d,可以得出a^2 <= n / 4, a^2 + b^ 2 <= n / 2; for (int i = 0; i * i * 4 <= n; i++) { for (int j = i; j * j + i * i <= n / 2; j++) { int t = n - i * i - j * j; if (h[t]) { int c = h[t] - 1; //防止开根号后因为精度关系,向下取整,例:25 开根号得到4.99999向下取整为4; int d = (sqrt(t - c * c) + 1e-4); printf("%d %d %d %d", i, j, c, d); return 0; } } } return 0; }
