拉格朗日四平方和定理 - 求最小平方和拆分

根据拉格朗日四平方和定理，任意一个非负整数都可以表示成四个非负整数的平方和。例如 5 = 0^2 + 0^2 + 1^2 + 2^2。给定一个正整数 n，请你将 n 拆分成 a^2+b^2+c^2+d^2，问 a+b+c+d 最小是多少？

输入格式

一个正整数表示 n。

输出格式

一个正整数表示答案。

样例输入1

4

样例输出1

2

约定

1<=n<=90000

解题思路

根据拉格朗日四平方和定理，任意一个非负整数都可以表示成四个非负整数的平方和。要使 a+b+c+d 最小，可以考虑将 n 拆分成尽可能多的完全平方数。

首先，可以先找到 n 以内的所有完全平方数。可以通过循环 i 从 0 开始，计算 i 的平方，并将平方数存储在一个数组中。

然后，使用动态规划的思想来求解最小的 a+b+c+d。

创建一个长度为 n+1 的数组 dp，其中 dp[i] 表示拆分完全平方数和为 i 所需的最小个数。

初始时，将 dp[0] 设置为 0，表示拆分和为 0 的完全平方数个数为 0。

接下来，从 1 到 n，遍历数组 dp，对于每个 i，遍历完全平方数数组，找到小于等于 i 的平方数 j，并更新 dp[i] = min(dp[i], dp[i-j]+1)。

最后，返回 dp[n]，即为答案。

代码实现如下

import math
n = int(input())
找到 n 以内的所有完全平方数
squares = []
for i in range(int(math.sqrt(n)) + 1):
squares.append(i*i)
动态规划求解最小的 a+b+c+d
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
for j in squares:
if j > i:
break
dp[i] = min(dp[i], dp[i - j] + 1)
print(dp[n])

复杂度分析

对于给定的 n，需要计算 n 以内的所有完全平方数，时间复杂度为 O(sqrt(n))。

然后，使用动态规划的思想求解最小的 a+b+c+d，需要遍历 n 次，每次遍历完全平方数数组，时间复杂度为 O(sqrt(n))。

因此，总的时间复杂度为 O(sqrt(n))。

空间复杂度为 O(n)，需要创建一个长度为 n+1 的数组 dp。