---
title: "5、四平方和"
created: 2025-11-28
tags:
  - 算法
---

# 5、四平方和

## 题目 [四平方和](https://www.acwing.com/problem/content/1223/)

![[image-14a4f15f.png]]

## 思路分析

（我只能说 这题暴力在蓝桥杯里面可以ac 不需要用二分或者哈希）

![[image-4cf68d72.png]]

求出三个后可以确定最后一个 三重循环暴力解决

其实求出两个 看差的一个t是否也能被两个凑出来 从而优化

这个看t是否能被两个凑出来 可以用二分 也可以直接用哈希

两个问题：

第一个问题：二分和哈希的代码b不是从a开始遍历，如何保证a <=b

第二个问题：二分和哈希的方式是如何保证b <= c的

两个问题都可以通过观察枚举顺序以及反证法来解答

第一个问题：假如存在一对a,b为答案，且a>b，那么b,a这一对数对在之前肯定已经枚举过的，因此找到的答案应该是b,a，因此这样并不会让找错答案，顶多是多枚举了一些

第二个问题：注意看二分和哈希分别做了什么事，二分是找到最小的大于等于n−a×a−b×b 的数对，哈希是找到等于n−a×a−b×b的数对，然后由枚举的顺序可以知道，a≤b,c≤d一定成立，且枚举的时候，a×a,b×b也是从小到大枚举的，换言之n−a×a−b×b是从大到小出现的，假设存在答案a,b,c,d，且b>c，那么一定有a×a+b×b>a×a+c×c，因此a,c应当比a,b先出现，而此时a,c,b,d是一组合法的答案。

## 代码实现

**暴力**$O(n^3)$

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N = 2500010;
int n;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    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(n2logNn)$

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N = 2500010;

struct Sum{
    int s, c, d;
    bool operator< (const Sum &t)const{
        if (s != t.s) return s < t.s;
        if (c != t.c) return c < t.c;
        return d < t.d;
    }
}sum[N];

int n, m;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    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 = 0; 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[l].s == t){
                printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }
    }
    return 0;
}
```

**哈希表**$O(n^2)$

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 2500010;
int n, m;
unordered_map<int, PII> S;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    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;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/二分相关模型/3、冶炼金属|3、冶炼金属]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/二分相关模型/5、递增三元组|5、递增三元组]]