Dado um número N , a tarefa é encontrar o número de quadraples tal que a ² + b ² = c ² + d ² onde (1 <= a, b, c, d <= N).

Exemplo:

Entrada: N = 2 
Saída: 6 
Explicação: 
Existem 6 quadraples 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 
Saída 28 
Explicação: 
Existem 28 quadraples válidos para N = 4. 

Abordagem ingênua: A abordagem ingênua é usar 4 loops aninhados no intervalo [1, N] e contar esses quádruplos (a, b, c, d) de modo que a ² + b ² = c ² + d ²

Complexidade de tempo: O (N ⁴ ) 
Espaço auxiliar: O (1)

Abordagem eficiente em vez da abordagem ingênua: a solução acima pode ser reduzida em termos de complexidade de tempo usando matemática. Encontre os quádruplos de modo que a ² + b ² = c ² + d ² .

a ² + b ² = c ² + d ² 
a ² + b ² - c ² = d ² 
Obtendo raiz quadrada em ambos os lados 
(a ² + b ² - c ² ) ^1/2 = d 

Usando a fórmula acima, podemos concluir que d existe apenas se (a ² + b ² - c ² ) ^1/2 for um número inteiro positivo. 

Complexidade de tempo: O (N ³ )

Abordagem eficiente: a ideia é usar Hashing . Abaixo estão as etapas: 

1. Percorra todos os pares (digamos (a, b) ) em [1, N] e armazene o valor de a ² + b ² com sua ocorrência em um mapa .
2. Repita todos os pares [1, N] e, se a soma existir no mapa, conte a soma de cada par armazenado no mapa.
3. Imprima a contagem.

Abaixo está a implementação da abordagem:

// 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

Complexidade de tempo: O (N ² log N)  
Espaço auxiliar: O (N)