2021-05-04: given a non negative integer C, you need to judge whether there are two integers a and B, so that a*a+b*b=c.

2021-05-04： Given a nonnegative integer c, You have to decide if there are two integers a and b, bring a_a+b_b=c.【 give an example 】c=5 when , return true.c=4 when , return true.c=3 when , return false.

Fuda answer 2021-05-04：

The sum of four squares Theorem . Time complexity ：O(sqrt(N)). Spatial complexity ：O(1).

1.n Always divide by 4, Until it's not divisible .

2.n%8, If yu 7, Go straight back to 4.

3. from 1 To sqrt(n) Start the cycle ,a_a+b_b=c When established ,a and b Not for 0, return 2;a and b There is one for 0, return 1.

4. return 3.

5. In the subject , The return value is 1 and 2 Yes. true. The return value is 3 and 4 Yes. false.

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "math"
)

func main() {
    for i := 1000; i <= 1100; i++ {
        ret := isSquares(i)
        fmt.Println(i, ret)
    }
}

//4+1+1+1
func isSquares(n int) bool {
    return numSquares(n) <= 2
}

func numSquares(n int) int {
    for n&3 == 0 { //n%4==0
        n >>= 2 //n/=4
    }
    if n&7 == 7 { //n%8==7
        return 4
    }
    a := 0
    for a*a <= n {
        b := int(math.Sqrt(float64(n - a*a)))
        if a > b {
            break
        }
        if a*a+b*b == n {
            ret := 0
            if a != 0 {
                ret++
            }
            if b != 0 {
                ret++
            }
            return ret
        }
        a += 1
    }
    return 3
}

The results are as follows ：

picture