Número de formas de escribir N como una suma de 4 cuadrados

Dado un número N, la tarea es encontrar el número de formas de escribir N como una suma de 4 cuadrados. Dos representaciones se consideran diferentes si sus términos están en un orden diferente o si el número entero elevado al cuadrado (no solo el cuadrado) es diferente.

Ejemplos:

Entrada: n=1 
Salida: 8 
1 ² + 0 ² + 0 ² + 0 ² 
0 ² + 1 ² + 0 ² + 0 ² 
0 ² + 0 ² + 1 ² + 0 ² 
0 ² + 0 ² + 0 ² + 1 ² 
De manera similar, hay otras 4 permutaciones posibles reemplazando 1 con -1 
Por lo tanto, hay 8 formas posibles.

Entrada: n=5 
Salida: 48 
 

Enfoque:  
el teorema de los cuatro cuadrados de Jacobi establece que el número de formas de escribir n como una suma de 4 cuadrados es 8 veces la suma del divisor de n si n es impar y es 24 veces la suma del divisor impar de n si n es par .Encuentre la suma de los divisores pares e impares de n ejecutando un ciclo de 1 a sqrt(n) .

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Number of ways of writing n
// as a sum of 4 squares
int sum_of_4_squares(int n)
{
    // sum of odd and even factor
    int i, odd = 0, even = 0;
 
    // iterate from 1 to the number
    for (i = 1; i <= sqrt(n); i++) {
        // if i is the factor of n
        if (n % i == 0) {
            // if factor is even
            if (i % 2 == 0)
                even += i;
 
            // if factor is odd
            else
                odd += i;
 
            // n/i is also a factor
            if ((n / i) != i) {
                // if factor is even
                if ((n / i) % 2 == 0)
                    even += (n / i);
 
                // if factor is odd
                else
                    odd += (n / i);
            }
        }
    }
    // if n is odd
    if (n % 2 == 1)
        return 8 * (odd + even);
 
    // if n is even
    else
        return 24 * (odd);
}
// Driver code
int main()
{
    int n = 4;
 
    cout << sum_of_4_squares(n);
 
    return 0;
}

// Java implementation of above approach
import java.io.*;
 
class GFG
{
     
// Number of ways of writing n
// as a sum of 4 squares
static int sum_of_4_squares(int n)
{
    // sum of odd and even factor
    int i, odd = 0, even = 0;
 
    // iterate from 1 to the number
    for (i = 1; i <= Math.sqrt(n); i++)
    {
        // if i is the factor of n
        if (n % i == 0)
        {
            // if factor is even
            if (i % 2 == 0)
                even += i;
 
            // if factor is odd
            else
                odd += i;
 
            // n/i is also a factor
            if ((n / i) != i)
            {
                // if factor is even
                if ((n / i) % 2 == 0)
                    even += (n / i);
 
                // if factor is odd
                else
                    odd += (n / i);
            }
        }
    }
    // if n is odd
    if (n % 2 == 1)
        return 8 * (odd + even);
 
    // if n is even
    else
        return 24 * (odd);
}
 
    // Driver code
    public static void main (String[] args)
    {
            int n = 4;
        System.out.println (sum_of_4_squares(n));
    }
}
 
// This code is contributed by tushil.

# Python3 implementation of above approach
 
# Number of ways of writing n
# as a sum of 4 squares
def sum_of_4_squares(n):
 
    # sum of odd and even factor
    i, odd, even = 0,0,0
 
    # iterate from 1 to the number
    for i in range(1,int(n**(.5))+1):
        # if i is the factor of n
        if (n % i == 0):
             
            # if factor is even
            if (i % 2 == 0):
                even += i
 
            # if factor is odd
            else:
                odd += i
 
            # n/i is also a factor
            if ((n // i) != i):
                 
                # if factor is even
                if ((n // i) % 2 == 0):
                    even += (n // i)
 
                # if factor is odd
                else:
                    odd += (n // i)
             
         
     
    # if n is odd
    if (n % 2 == 1):
        return 8 * (odd + even)
 
    # if n is even
    else :
        return 24 * (odd)
 
# Driver code
 
n = 4
 
print(sum_of_4_squares(n))
 
# This code is contributed by mohit kumar 29

// C# implementation of above approach
using System;
 
class GFG
{
         
// Number of ways of writing n
// as a sum of 4 squares
static int sum_of_4_squares(int n)
{
    // sum of odd and even factor
    int i, odd = 0, even = 0;
 
    // iterate from 1 to the number
    for (i = 1; i <= Math.Sqrt(n); i++)
    {
        // if i is the factor of n
        if (n % i == 0)
        {
            // if factor is even
            if (i % 2 == 0)
                even += i;
 
            // if factor is odd
            else
                odd += i;
 
            // n/i is also a factor
            if ((n / i) != i)
            {
                // if factor is even
                if ((n / i) % 2 == 0)
                    even += (n / i);
 
                // if factor is odd
                else
                    odd += (n / i);
            }
        }
    }
    // if n is odd
    if (n % 2 == 1)
        return 8 * (odd + even);
 
    // if n is even
    else
        return 24 * (odd);
}
 
// Driver code
static public void Main ()
{
         
    int n = 4;
    Console.WriteLine(sum_of_4_squares(n));
}
}
 
// This code is contributed by ajit.

<script>
 
// Javascript implementation of above approach
 
// Number of ways of writing n
// as a sum of 4 squares
function sum_of_4_squares(n)
{
     
    // Sum of odd and even factor
    var i, odd = 0, even = 0;
 
    // Iterate from 1 to the number
    for(i = 1; i <= Math.sqrt(n); i++)
    {
         
        // If i is the factor of n
        if (n % i == 0)
        {
             
            // If factor is even
            if (i % 2 == 0)
                even += i;
 
            // If factor is odd
            else
                odd += i;
 
            // n/i is also a factor
            if ((n / i) != i)
            {
                 
                // If factor is even
                if ((n / i) % 2 == 0)
                    even += (n / i);
 
                // If factor is odd
                else
                    odd += (n / i);
            }
        }
    }
     
    // If n is odd
    if (n % 2 == 1)
        return 8 * (odd + even);
 
    // If n is even
    else
        return 24 * (odd);
}
 
// Driver code
var n = 4;
 
document.write(sum_of_4_squares(n));
 
// This code is contributed by SoumikMondal
 
</script>

24

Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)