這里介紹下數(shù)論中的勒讓德三平方和定理、拉格朗日四平方和定理。并介紹如何巧妙利用它進(jìn)行解決問題

基本原理

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

拉格朗日四平方和定理，也被稱為Bachet猜想。該定理指出任一自然數(shù)都可以表示為四個整數(shù)平方之和。該定理由拉格朗日于1770年證明。即：

舉個栗子，如下所示

「2. 勒讓德三平方和定理」

勒讓德三平方和定理指出如果一個自然數(shù)n符合下述條件時，則可以表示為三個整數(shù)平方之和。其中a、b均為非負(fù)整數(shù)

實踐

學(xué)習(xí)過程中要善于理論聯(lián)系實際。故在介紹完勒讓德三平方和定理、拉格朗日四平方和定理后，現(xiàn)在我們來進(jìn)行實踐。這里以LeetCode的第279題——完全平方數(shù) 為例

給你一個整數(shù) n ，返回 和為 n 的完全平方數(shù)的最少數(shù)量 完全平方數(shù) 是一個整數(shù)，其值等于另一個整數(shù)的平方；換句話說，其值等于一個整數(shù)自乘的積。例如，1、4、9 和 16 都是完全平方數(shù)，而 3 和 11 不是

示例 1 

輸入：n = 12

輸出：3

解釋：12 = 4 + 4 + 4

示例 2 

輸入：n = 13

輸出：2

解釋：13 = 4 + 9  

 

提示 1 <= n <= 104

首先說明該題可通過動態(tài)規(guī)劃解決，但這里為了說明上述兩個定理的應(yīng)用。故我們采用數(shù)學(xué)解法。具體地：

1. 當(dāng)n滿足4^k*(8m+7)形式時，由于不滿足勒讓德三平方和定理。同時結(jié)合拉格朗日四平方和定理易知，此時直接返回4即可
2. 當(dāng)n不滿足4^k*(8m+7)形式時，即滿足勒讓德三平方和定理。則此時答案只能會是1、2、3中的一個
• 如果n為一個完全平方數(shù)，則此時答案必然為1
• 如果n滿足a^2+b^2形式，即答案為2。則我們只需對所有的a進(jìn)行枚舉，其中a的范圍為[1, √n]。然后判斷n-a^2是否為完全平方數(shù)即可
• 如果排除了上述所有情形，則答案只能為3。即n滿足a^2+b^2+c^2形式

此時，我們不難通過Java實現(xiàn)上述思路。代碼如下所示

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;
    }

    /**
     * 判斷是否為完全平方數(shù)
     * @param n
     * @return
     */
    private boolean isSquare(int n) {
        int x = (int)Math.sqrt(n);
        boolean res = ( x*x == n);
        return res;
    }
}