【题目典例】四平方和

博主： Fivk
发布时间：2022 年 02 月 06 日
938 次浏览
349字数
分类：题目典例算法基础

### 题目描述

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 `4` 个正整数的平方和。

如果把 `0` 包括进去，就正好可以表示为 `4` 个数的平方和。

比如：

$5=0^2+0^2+1^2+2^2$

$7=1^1+1^1+1^1+2^2$

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 `4` 个数排序：

$0≤a≤b≤c≤d$

并对所有的可能表示法按 $a,b,c,d$ 为联合主键升序排列，最后输出第一个表示法。

### 输入格式

输入一个正整数 `N`。

### 输出格式

输出 `4`个非负整数，按从小到大排序，中间用空格分开。

### 数据范围

$0<N<5{\times}10^6$

### 输入样例：

```
5
```

### 输出样例：

```
0 0 1 2
```

### 算法分析

$a,b,c,d{\leqslant}N=5{\times}10^6$

$\sqrt(N)=2236.067977$故最多只能枚举两位数($2236^{2236} {\geq}1{\times}10^8$)

故:

1. 最多只能枚举2个数
2. 空间换时间

#### 第一步：空间换时间方法

```cpp
for (c = 0; pow(c, 2) <= N; c ++)
    for (d = c; pow(c, 2) + pow(d, 2) <= N; d ++)
        // 存放c^2 + d^2的值
```

将所有的$c^2+d2$存起来$O(N^2)$

#### 第二步：枚举

```cpp
for (a = 0; pow(a, 2) <= N; a ++)
    for (b = a; pow(b, 2) + pow(c, 2) <= N; b ++)
        t = n - pow(c, 2) - pow(d, 2);
```

`t`表示和最终答案的差是多少$O(N^2)$
此时我们只需要去判断一下这个 `t`能否用两个数的平方和凑出来即可，
即得到 `t`后**寻找**前面$c^2+d2$的值，是否存在与t相等的值。

```cpp
if (存在与t相等的值)
    // 输出answer
```

寻找方法：

1. 哈希$O(1)$
2. 二分$O(logn)$

#### 第三步：找到字典序最小解

分析：对于 `a`和 `b`，是两个 `for`循环找到的最小的值，因此前两个数可以保证字典序最小。
所以现在我们只需要找到后两个字典序最小的组合即可。
故存放的时候我们不仅要存放$c^2+d^2$的值，还要按照 `c,d`的字典序排先后顺序。

### AC代码

#### 暴力做法：$O(N^3)$ 超时

```cpp
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2500010;

int n;

int main()
{
    cin >> n;
    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 t = n - a * a - b * b - c * c;
                int d = sqrt(t);
                if (d * d == t)
                {
                    printf("%d %d %d %d\n", a, b, c, d);
                    return 0;
                }
            }
}
```

#### 二分查找：$O(N^2logN)$ 2747 ms

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 5 * 1e6 + 10;
int n, x;
int a, b, c, d;

struct val {
    int t, x, y;
};

val V[N];
int m;

bool cmp(val v1, val v2) {
    if (v1.t != v2.t) {
        return v1.t < v2.t;
    } else if (v1.x != v2.x) {
        return v1.x < v2.x;
    } else {
        return v1.t < v2.t;
    }
}

int main() {
  
	scanf("%d", &n);
  
    // 存放放c^2和d^2的值
    for (c = 0; c * c <= n; c ++) {
        for (d = c; c * c + d * d <= n; d ++) {  
            // 使用数组存放c^2和d^2的值和数据
            V[m ++] = {c * c + d * d, c, d};
        }
    }
  
    // 二分查找需要有序
    sort(V, V + m, cmp);

//枚举
    for (a = 0; a * a <= n; a ++) {
        for (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 (V[mid].t >= t) r = mid;
                else l = mid + 1;
            }
  
            if (V[l].t == t) {
                printf("%d %d %d %d", a, b, V[l].x, V[l].y);
                exit(0);
            }
        }
    }
	return 0;
}
```

#### 哈希表$O(N^2)$ 超时

```cpp
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 2500010;

int n, m;
unordered_map<int, PII> S;

int main()
{
    cin >> n;

for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ )
        {
            int t = c * c + d * d;
            if (S.count(t) == 0) S[t] = {c, d};
        }

for (int a = 0; a * a <= n; a ++ )
        for (int b = 0; a * a + b * b <= n; b ++ )
        {
            int t = n - a * a - b * b;
            if (S.count(t))
            {
                printf("%d %d %d %d\n", a, b, S[t].x, S[t].y);
                return 0;
            }
        }

return 0;
}
```

#### 大佬使用air数组直接做的 395 ms

```cpp
#include<iostream>
#include<map>
using namespace std;

const int MAX=5e6+5;
int n;
pair<int,int> a[MAX];

int main()
{
    cin>>n;
    for(int i=0;i*i<=n;i++)
    {
        for(int j=i;i*i+j*j<=n;j++)
        {
             int t=i*i+j*j;
             if(a[t].second==0&&a[t].first==0)
             {
                 a[t]={i,j};
             }
        }
    }
    for(int i=0;i*i<=n;i++)
    {
        for(int j=i;j*j+i*i<=n;j++)
        {
            int t=n-i*i-j*j;
            if(a[t].second!=0||a[t].first!=0)
            {
                cout<<i<<" "<<j<<" "<<a[t].first<<" "<<a[t].second;
                return 0;
            }
        }
    }
    return 0;
}
```

最后修改：2022 年 02 月 08 日

如果觉得我的文章对你有用，请随意赞赏

【题目典例】四平方和

Fivk • 2022 年 02 月 06 日

### 题目描述

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 `4` 个正整数的平方和。

如果把 `0` 包括进去，就正好可以表示为 `4` 个数的平方和。

比如：

$5=0^2+0^2+1^2+2^2$

$7=1^1+1^1+1^1+2^2$

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 `4` 个数排序：

$0≤a≤b≤c≤d$

并对所有的可能表示法按 $a,b,c,d$ 为联合主键升序排列，最后输出第一个表示法。

### 输入格式

输入一个正整数 `N`。

### 输出格式

输出 `4`个非负整数，按从小到大排序，中间用空格分开。

### 数据范围

$0<N<5{\times}10^6$

### 输入样例：

```
5
```

### 输出样例：

```
0 0 1 2
```

### 算法分析

$a,b,c,d{\leqslant}N=5{\times}10^6$

$\sqrt(N)=2236.067977$故最多只能枚举两位数($2236^{2236} {\geq}1{\times}10^8$)

故:

1. 最多只能枚举2个数
2. 空间换时间

#### 第一步：空间换时间方法

```cpp
for (c = 0; pow(c, 2) <= N; c ++)
    for (d = c; pow(c, 2) + pow(d, 2) <= N; d ++)
        // 存放c^2 + d^2的值
```

将所有的$c^2+d2$存起来$O(N^2)$

#### 第二步：枚举

```cpp
for (a = 0; pow(a, 2) <= N; a ++)
    for (b = a; pow(b, 2) + pow(c, 2) <= N; b ++)
        t = n - pow(c, 2) - pow(d, 2);
```

```cpp
if (存在与t相等的值)
    // 输出answer
```

寻找方法：

1. 哈希$O(1)$
2. 二分$O(logn)$

#### 第三步：找到字典序最小解

### AC代码

#### 暴力做法：$O(N^3)$ 超时

```cpp
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2500010;

int n;

#### 二分查找：$O(N^2logN)$ 2747 ms

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 5 * 1e6 + 10;
int n, x;
int a, b, c, d;

struct val {
    int t, x, y;
};

val V[N];
int m;

bool cmp(val v1, val v2) {
    if (v1.t != v2.t) {
        return v1.t < v2.t;
    } else if (v1.x != v2.x) {
        return v1.x < v2.x;
    } else {
        return v1.t < v2.t;
    }
}

#### 哈希表$O(N^2)$ 超时

```cpp
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 2500010;

int n, m;
unordered_map<int, PII> S;

int main()
{
    cin >> n;

for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ )
        {
            int t = c * c + d * d;
            if (S.count(t) == 0) S[t] = {c, d};
        }

return 0;
}
```

#### 大佬使用air数组直接做的 395 ms

```cpp
#include<iostream>
#include<map>
using namespace std;

const int MAX=5e6+5;
int n;
pair<int,int> a[MAX];

【题目典例】四平方和

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【微服务】elasticsearch分布式搜索引擎（上）

【C】全排列问题

【C】理解什么是指针、指针符号 & *

【C】文件_文件的随机读写(rewind ，ftell，fseek)

【SpringCache】通用缓存使用与注解介绍（快速入门）

【题目典例】四平方和