大家好，欢迎来到IT知识分享网。

目录

一，拉格朗日四平方和定理

二，证明过程

三，推论

四，OJ实战

CSU 1404 Four-square Theorem

力扣 279. 完全平方数

一，拉格朗日四平方和定理

每个正整数均可表示为4个整数的平方和

二，证明过程

1，欧拉恒等式

2，

3，任意素数都可以表示为四平方和

三，推论

形如4^a * (8k+7)的数不能表示成三平方和，其他形式的数都可以表示成三平方和。

四，OJ实战

CSU 1404 Four-square Theorem

题目：

Description
Lagrange’s four-square theorem states that any natural number can be represented as the sum of four integer squares: n = a2 + b2 + c2 + d2. For example, 3, 31 and 310 can be represented as the sum of four squares as follows: 3 = 12 + 12 + 12 + 02, 31 = 52 + 22 + 12 + 12, 310 = 172 + 42 + 22 + 12.
Given an integer n, represent it by the sum of four integer squares.
This result may be helpful: Any integer n which is not of the form 4a(8m + 7) can be written as a sum of three squares, where a and m are arbitrary non-negative integers. For illustration, 7 = 40 * (8 * 0 + 7), so 7 can not be written as a sum of three squares.
Input
The first line contains the number of test cases T (1 <= T <= 104).
For each test case, there is only one line with an integer n (1 <= n <= 109).
Output
For each test case, output four integers a, b, c, d separated by a single space which satisfy n2 = a2 + b2 + c2 + d2. If there are multiple solutions, anyone will be accepted.

Sample Input
5
1
7
7
10
10
Sample Output
1 0 0 0
1 1 1 2
1 2 1 1
1 0 3 0
2 1 1 2

思路：

本来我的思路是利用欧拉四平方和恒等式，不过并没有什么效果，遇到8m+7型的大素数就直接变成暴力枚举了。

这个题目主要是根据给的提示，把不能表示成3个平方和的数拆分成一个尽量大的平方和加上一个可以表示成3个平方和的数

然后再暴力枚举

代码：

#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
 
bool g(int n)
{
	while (n % 4 == 0)n /= 4;
	return n % 8 == 7;
}
 
void f(int n)
{
	for (int a = int(sqrt(n));; a--)
	{
		n -= a*a;
		if (n && g(n))
		{
			n += a*a;
			continue;
		}
		for (int b = 0; b*b <= n; b++)
		{
			n -= b*b;
			for (int c = 0; c <= b && c*c <= n; c++)
			{
				n -= c*c;
				int d = int(sqrt(n));
				if (n == d*d)
				{
					printf("%d %d %d %d\n", a, b, c, d);
					return;
				}
				n += c*c;
			}
			n += b*b;
		}		
	}	
}
 
int main()
{
	int t, n;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		f(n);
	}
	return 0;
}

力扣 279. 完全平方数

题目：

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.
示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

思路一：

动态规划，枚举n的平方和组成中可能出现的值，只要枚举一个即可化为子问题。

代码：
 

class Solution {
public:
    int numSquares(int n) {
        static map<int,int>m;
        if(m[n])return m[n];
        m[n]=n;
        for(int i=1;i*i<=n;i++)m[n]=min(m[n],numSquares(n-i*i)+1);
        return m[n];
    }
};

时间复杂度：O（n^(3/2)）

思路二：

用拉格朗日四平方和定理，所有的数都是四平方和。

判断一个数是不是平方数，如果不是的话，是不是平方和，如果不是的话，是不是三平方和，如果不是三平方和，那就是4。

先算出所有的平方，以及所有的平方和，然后用双指针扫描一遍看有没有加起来是n的。

时间复杂度O（n）

思路三：

用四平方和定理的推论，形如4^a * (8k+7)的数不能表示成三平方和，其他形式的数都可以表示成三平方和

只需要判断一个数是不是平方和即可。

用双指针的话，时间复杂度O（ sqrt（n））

暴力枚举平方和的话，O（n）

bool g(int n)
{
    while (n % 4 == 0)n /= 4;
    return n % 8 == 7;
}

class Solution {
public:
    int numSquares(int n) {
        if(g(n))return 4;
        if(int(sqrt(n))*int(sqrt(n))==n)return 1;
        for(int i=0;i<=100;i++)for(int j=0;j<=i;j++)if(n==i*i+j*j)return 2;
        return 3;
    }
};