拉格朗日四平方和定理CSU 1404: Four-square Theorem
目录
一，拉格朗日四平方和定理
每个正整数均可表示为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;
-
}
-
};
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/115683823
- 点赞
- 收藏
- 关注作者
评论（0）