摘要
Title: 1221. 四平方和
Tag: 哈希表、空间换时间
Memory Limit: 64 MB
Time Limit: 1000 ms

1221. 四平方和

题意

四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。
0<N<5∗10^6
思路
- 先看数据范围，a,b,c,d不会超过 $\sqrt{n}$ , 所以最多在 $2300$ 左右，但是不可能枚举三个超过1e3的数
- 所以采取空间换时间，先把求过的 $a^2 + b^2$ 算出来，并用哈希表存下来，接着枚举哈希表中的元素即可，如果 $d[i]$ 和 $d[n - i]$ 同时存在，说明找到第一组解了，一定是最小的，直接输出即可
- ps：一定要看清楚题目要求！！ 求出最小的，所以a, b, c, d也是最小的，所以在存哈希表时，就要判断是否要取代这个数
  - 比如 $6^2 + 8^2 = 100$ , $0 ^ 2 + 10 ^ 2 = 100$ ，但是明显 $0, 10$ 字典序更小

代码

'''
Author: NEFU AB-IN
Date: 2022-03-22 20:26:55
FilePath: \ACM\Acwing\1221.py
LastEditTime: 2022-03-22 21:17:54
'''
from math import sqrt
from collections import Counter

n = int(input())

N = int(sqrt(n))
d = Counter()

for i in range(N + 1):
    for j in range(i, N + 1):
        res = i * i + j * j
        if res <= n and (not d[res] or [i, j] < d[res]):
            d[res] = [i, j]

ans = []
st = Counter()

for i in d.keys():
    if d[n - i]:
        a, b = d[i]
        c, d = d[n - i]
        print(a, b, c, d)
        exit(0)

1221. 四平方和

题意

思路

代码