18 条题解
-
29
P1011 四平方和
题目描述
四平方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去,就正好可以表示为 4 个数的平方和。
对于一个给定的正整数,可能存在多种平方和的表示法。
要求你对 4 个数排序使得 0≤a≤b≤c≤d。
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法。
思路
判断谁都会:
for(int a = 0;a * a <= n;a++) { for(int b = 0;b * b <= n;b++) { for(int c = 0;c * c <= n;c++) { for(int d = 0;d * d <= n;d++) { if(a * a + b * b + c * c + d * d == n) { cout << a << " " << b << " " << c << " " << d; } } } } }
但:
优化!
主要是优化一下a,b,c,d的上限。
a有4个数,并且递增,那上限是n / 4;
b有3个数,并且递增,那上限是n / 3;
c有2个数,并且递增,那上限是n / 2;
d有1个数,并且递增,那上限是n / 1,n;
for(int a = 0;a * a <= n / 4;a++) { for(int b = 0;b * b <= n / 3;b++) { for(int c = 0;c * c <= n / 2;c++) { for(int d = 0;d * d <= n;d++) { if(a * a + b * b + c * c + d * d == n) { cout << a << " " << b << " " << c << " " << d; } } } } }
......
为啥?return 0!
已经找到了,却还要枚举完?
for(int a = 0;a * a <= n / 4;a++) { for(int b = 0;b * b <= n / 3;b++) { for(int c = 0;c * c <= n / 2;c++) { for(int d = 0;d * d <= n;d++) { if(a * a + b * b + c * c + d * d == n) { cout << a << " " << b << " " << c << " " << d; return 0; } } } } }
一番核对后发现data没问题,时间罗。
一番检查
long long!!!!!!!!!!!!!!!!!!!!!!!!!
参考代码:
#include <iostream>//hetao3097453 using namespace std; int main() { long long n; cin >> n; for(long long a = 0;a * a <= n / 4;a++) { for(long long b = 0;b * b <= n / 3;b++) { for(long long c = 0;c * c <= n / 2;c++) { for(long long d = 0;d * d <= n;d++) { if(a * a + b * b + c * c + d * d == n) { cout << a << " " << b << " " << c << " " << d; return 0; } } } } } return 0; }
hetao3097453(Bilililil @ 一钩出站)
2023年3月25日
信息
- ID
- 50
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 3387
- 已通过
- 1374
- 上传者