xyZGHio

本是青灯不归客,却因浊酒恋风尘

0%

浅谈勒让德三平方和定理、拉格朗日四平方和定理

这里介绍下数论中的勒让德三平方和定理、拉格朗日四平方和定理。并介绍如何巧妙利用它进行解决问题

abstract.jpeg

基本原理

1. 拉格朗日四平方和定理

拉格朗日四平方和定理,也被称为Bachet猜想。该定理指出任一自然数都可以表示为四个整数平方之和。该定理由拉格朗日于1770年证明。即:

figure 1.png

举个栗子,如下所示

figure 2.png

2. 勒让德三平方和定理

勒让德三平方和定理指出如果一个自然数n符合下述条件时,则可以表示为三个整数平方之和。其中a、b均为非负整数

figure 3.png

实践

学习过程中要善于理论联系实际。故在介绍完勒让德三平方和定理、拉格朗日四平方和定理后,现在我们来进行实践。这里以LeetCode的第279题——完全平方数 为例

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是

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

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

提示
1 <= n <= 104

首先说明该题可通过动态规划解决,但这里为了说明上述两个定理的应用。故我们采用数学解法。具体地:

  1. 当n满足4^k*(8m+7)形式时,由于不满足勒让德三平方和定理。同时结合拉格朗日四平方和定理易知,此时直接返回4即可
  2. 当n不满足4^k*(8m+7)形式时,即满足勒让德三平方和定理。则此时答案只能会是1、2、3中的一个
    • 如果n为一个完全平方数,则此时答案必然为1
    • 如果n满足a^2+b^2形式,即答案为2。则我们只需对所有的a进行枚举,其中a的范围为[1, √n]。然后判断n-a^2是否为完全平方数即可
    • 如果排除了上述所有情形,则答案只能为3。即n满足a^2+b^2+c^2形式

此时,我们不难通过Java实现上述思路。代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public int numSquares(int n) {
// 如果不满足 勒让德三平方和定理, 则其必然只能满足 拉格朗日四平方和定理
// 即: n = a*a + b*b + c*c + d*d
if( checkAnswer4(n) ) {
return 4;
}

// 判断是否为 n = a*a 场景
if( isSquare(n) ) {
return 1;
}

// 判断是否为 n = a*a + b*b 场景
for (int a=1; a*a<=n; a++) {
int b = n - a*a;
if( isSquare(b) ) {
return 2;
}
}

// 由于满足勒让德三平方和定理条件, 故此时只可能为3
// 即: n = a*a + b*b + c*c
return 3;
}

/**
* 判断n是否能表示为 4^k*(8m+7) 形式, 即不满足 勒让德三平方和定理
* @param n
* @return
*/
private boolean checkAnswer4(int n) {
while ( n%4==0 ) {
n = n / 4;
}

boolean res = (n%8 == 7);
return res;
}

/**
* 判断是否为完全平方数
* @param n
* @return
*/
private boolean isSquare(int n) {
int x = (int)Math.sqrt(n);
boolean res = ( x*x == n);
return res;
}
}
请我喝杯咖啡捏~
  • 本文作者: Aaron Zhu
  • 本文链接: https://xyzghio.xyz/SquareSum/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-ND 许可协议。转载请注明出处!

欢迎关注我的微信公众号:青灯抽丝