Contar cuatrillizos (A, B, C, D) hasta N tal que la suma de los cuadrados de A y B sea igual a la de C y D

Dado un número N , la tarea es encontrar el número de cuádruples tales que a ² + b ² = c ² + d ² donde (1 <= a, b, c, d <= N).

Ejemplo:

Entrada: N = 2 
Salida: 6 
Explicación: 
Hay 6 cuádruples válidos (1, 1, 1, 1), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 2, 2).

Entrada: N = 4 
Salida 28 
Explicación: 
Hay 28 cuádruples válidos para N = 4. 

Enfoque ingenuo: el enfoque ingenuo es usar 4 bucles anidados en el rango [1, N] y contar esos cuatrillizos (a, b, c, d) de tal manera que a ² + b ² = c ² + d ²

Complejidad de Tiempo: O(N ⁴ ) 
Espacio Auxiliar: O(1)

Enfoque eficiente en lugar del enfoque ingenuo: la solución anterior se puede reducir en términos de complejidad de tiempo usando algunas matemáticas. Encuentra los cuatrillizos tales que a ² + b ² = c ² + d ² .

a ² + b ² = c ² + d ² 
a ² + b ² – c ² = d ² 
Sacando raíces cuadradas en ambos lados 
(a ² + b ² – c ² ) ^1/2 = d 

Usando la fórmula anterior, podemos concluir que d existe solo si (a ² + b ² – c ² ) ^1/2 es un número entero positivo. 

Complejidad temporal: O(N ³ )

Enfoque Eficiente: La idea es usar Hashing . A continuación se muestran los pasos: 

1. Recorra todos los pares (digamos (a, b) ) sobre [1, N] y almacene el valor de a ² + b ² con su aparición en un Map .
2. Itere sobre todos los pares [1, N] y, si la suma existe en el mapa, cuente la suma de cada par almacenado en el mapa.
3. Imprime el conteo.

A continuación se muestra la implementación del enfoque:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
// Function to count the quadruples
ll countQuadraples(ll N)
{
    // Counter variable
    ll cnt = 0;
 
    // Map to store the
    // sum of pair (a^2 + b^2)
    map<ll, ll> m;
 
    // Iterate till N
    for (ll a = 1; a <= N; a++) {
 
        for (ll b = 1; b <= N; b++) {
 
            // Calculate a^2 + b^2
            ll x = a * a + b * b;
 
            // Increment the value in map
            m[x] += 1;
        }
    }
 
    for (ll c = 1; c <= N; c++) {
        for (ll d = 1; d <= N; d++) {
 
            ll x = c * c + d * d;
 
            // Check if this sum
            // was also in a^2 + b^2
            if (m.find(x) != m.end())
                cnt += m[x];
        }
    }
 
    // Return the count
    return cnt;
}
 
// Driver Code
int main()
{
    // Given N
    ll N = 2;
 
    // Function Call
    cout << countQuadraples(N)
        << endl;
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count the quadruples
static long countQuadraples(long N)
{
     
    // Counter variable
    long cnt = 0;
 
    // Map to store the
    // sum of pair (a^2 + b^2)
    Map<Long, Long> m = new HashMap<>();
 
    // Iterate till N
    for(long a = 1; a <= N; a++)
    {
        for(long b = 1; b <= N; b++)
        {
             
            // Calculate a^2 + b^2
            long x = a * a + b * b;
 
            // Increment the value in map
            m.put(x, m.getOrDefault(x, 0l) + 1);
        }
    }
     
    for(long c = 1; c <= N; c++)
    {
        for(long d = 1; d <= N; d++)
        {
            long x = c * c + d * d;
 
            // Check if this sum
            // was also in a^2 + b^2
            if (m.containsKey(x))
                cnt += m.get(x);
        }
    }
     
    // Return the count
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given N
    long N = 2;
     
    // Function call
    System.out.println(countQuadraples(N));
}
}
 
// This code is contributed by offbeat

# Python3 program for
# the above approach
from collections import defaultdict
 
# Function to count
# the quadruples
def countQuadraples(N):
 
    # Counter variable
    cnt = 0
  
    # Map to store the
    # sum of pair (a^2 + b^2)
    m = defaultdict (int)
  
    # Iterate till N
    for a in range (1, N + 1):
  
        for b in range (1, N + 1):
  
            # Calculate a^2 + b^2
            x = a * a + b * b
  
            # Increment the value in map
            m[x] += 1
  
    for c in range (1, N + 1):
        for d in range (1, N + 1):
  
            x = c * c + d * d
  
            # Check if this sum
            # was also in a^2 + b^2
            if x in m:
                cnt += m[x]
         
    # Return the count
    return cnt
  
# Driver Code
if __name__ == "__main__":
 
    # Given N
    N = 2
  
    # Function Call
    print (countQuadraples(N))
         
# This code is contributed by Chitranayal

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to count the quadruples
static long countQuadraples(long N)
{
     
    // Counter variable
    long cnt = 0;
 
    // Map to store the
    // sum of pair (a^2 + b^2)
    Dictionary<long,
               long> m = new Dictionary<long,
                                        long>();
 
    // Iterate till N
    for(long a = 1; a <= N; a++)
    {
        for(long b = 1; b <= N; b++)
        {
             
            // Calculate a^2 + b^2
            long x = a * a + b * b;
 
            // Increment the value in map
            if (m.ContainsKey(x))
                m[x] = m[x] + 1;
            else
                m.Add(x, 1);
        }
    }
     
    for(long c = 1; c <= N; c++)
    {
        for(long d = 1; d <= N; d++)
        {
            long x = c * c + d * d;
 
            // Check if this sum
            // was also in a^2 + b^2
            if (m.ContainsKey(x))
                cnt += m[x];
        }
    }
     
    // Return the count
    return cnt;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given N
    long N = 2;
     
    // Function call
    Console.WriteLine(countQuadraples(N));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
 
// Javascript program for the above approach
 
// Function to count the quadruples
function countQuadraples(N)
{
    // Counter variable
    var cnt = 0;
 
    // Map to store the
    // sum of pair (a^2 + b^2)
    var m = new Map(); 
 
    // Iterate till N
    for (var a = 1; a <= N; a++) {
 
        for (var b = 1; b <= N; b++) {
 
            // Calculate a^2 + b^2
            var x = a * a + b * b;
 
            // Increment the value in map
            if(m.has(x))
                m.set(x, m.get(x)+1)
            else
                m.set(x, 1)
        }
    }
 
    for (var c = 1; c <= N; c++) {
        for (var d = 1; d <= N; d++) {
 
            var x = c * c + d * d;
 
            // Check if this sum
            // was also in a^2 + b^2
            if (m.has(x))
                cnt += m.get(x);
        }
    }
 
    // Return the count
    return cnt;
}
 
// Driver Code
// Given N
var N = 2;
// Function Call
document.write( countQuadraples(N))
 
 
</script>

6

Complejidad de Tiempo: O(N ² log N)  
Espacio Auxiliar: O(N)