2522 四平方和
大约 2 分钟
2522 四平方和
【算法】 枚举、剪枝
【C++】 循环、sqrt
【难度】 入门
一、题目简述
四平方和定理:每个正整数可表示为 个非负整数的平方和:。
给定正整数 (),求字典序最小的一组解 。
字典序最小:从左到右比较,先让 尽可能小,再让 尽可能小,以此类推。
二、解题思路
四重循环枚举 会超时。注意到字典序最小的要求,可以用三重循环:前三个确定后, 可以直接算出来。
从小到大枚举 ,计算 ,判断是否是完全平方数。
由于 ,。三重循环最坏 会超时。但实际会提前找到解退出,不会跑满。
优化:枚举 从 0 到 , 从 到 , 从 到 ,保证非递减且尽早剪枝。
但最简单的写法(枚举 a,b,c 到 sqrt(n),找到就退出)在实际数据下也能过,因为 时枚举量有限。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// 枚举 a, b, c,计算 d
for (int a = 0; a * a <= n; a++) {
for (int b = a; a * a + b * b <= n; b++) {
for (int c = b; a * a + b * b + c * c <= n; c++) {
int d2 = n - a * a - b * b - c * c;
int d = sqrt(d2);
if (d * d == d2) {
cout << a << " " << b << " " << c << " " << d << endl;
return 0;
}
}
}
}
return 0;
}四、复杂度分析
- 时间:实际远小于 。 时 ,但循环中 且 且提前退出,平均情况很快。最坏情况(如 需要较大的 )也能在时限内完成。
- 空间:。
五、易错点
- 要求字典序最小,所以从小到大枚举,找到的第一个解就是答案。
- 判断完全平方数:
int d = sqrt(d2); if (d * d == d2)注意用整数 sqrt。
