Cuenta de pares de enteros cuya diferencia de cuadrados es igual a N

Dado un entero positivo N , la tarea es encontrar el número de pares de enteros (x, y) cuya diferencia de cuadrados sea igual a N, es decir, 

Ejemplos: 

Entrada: N = 20 
Salida: 4 
Explicación: 
Los 4 pares posibles son (10, 2), (-10, 2), (-10, -2) y (10, -2).

Entrada: N = 80 
Salida: 12 
Explicación: 
Los 12 pares posibles son: 
1. (40, 2), (-40, 2), (-40, -2) y (40, -2). 
2. (20, 4), (-20, 4), (-20, -4) y (20, -4). 
3. (10, 8), (-10, 8), (-10, -8) y (10, -8). 
 

Enfoque: 
La ecuación dada también se puede escribir como:  

=> 
=>  

Ahora para una solución integral de la ecuación dada:  

(x+y)(xy) 

es siempre un número entero 
=> (x+y)(xy) 
 son divisores de N 
  

Sean (x + y) = p1 y (x + y) = p2 
las dos ecuaciones donde p1 y p2 son los divisores de N 
tales que p1 * p2 = N .

Resolviendo las dos ecuaciones anteriores tenemos:  

=> 
y 

De los cálculos anteriores, para que x e y sean integrales, entonces la suma de los divisores debe ser par . Dado que hay 4 valores posibles para dos valores de x e y como (+x, +y), (+x, -y), (-x, +y) y (-x, -y) . 
Por lo tanto, el número total de posibles soluciones viene dado por 4*(cuenta pares de divisores con suma par) .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the integral
// solutions of the given equation
void findSolutions(int N)
{
 
    // Initialise count to 0
    int count = 0;
 
    // Iterate till sqrt(N)
    for (int i = 1; i <= sqrt(N); i++) {
 
        if (N % i == 0) {
 
            // If divisor's pair sum is even
            if ((i + N / i) % 2 == 0) {
                count++;
            }
        }
    }
 
    // Print the total possible solutions
    cout << 4 * count << endl;
}
 
// Driver Code
int main()
{
    // Given number N
    int N = 80;
 
    // Function Call
    findSolutions(N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find the integral
// solutions of the given equation
static void findSolutions(int N)
{
 
    // Initialise count to 0
    int count = 0;
 
    // Iterate till sqrt(N)
    for(int i = 1; i <= Math.sqrt(N); i++)
    {
       if (N % i == 0)
       {
            
           // If divisor's pair sum is even
           if ((i + N / i) % 2 == 0)
           {
               count++;
           }
       }
    }
     
    // Print the total possible solutions
    System.out.print(4 * count);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given number N
    int N = 80;
     
    // Function Call
    findSolutions(N);
}
}
 
// This code is contributed by Shubham Prakash.

# Python3 program for the above approach
import math;
 
# Function to find the integral
# solutions of the given equation
def findSolutions(N):
 
    # Initialise count to 0
    count = 0;
 
    # Iterate till sqrt(N)
    for i in range(1, int(math.sqrt(N)) + 1):
 
        if (N % i == 0):
 
            # If divisor's pair sum is even
            if ((i + N // i) % 2 == 0):
                count += 1;
             
    # Print the total possible solutions
    print(4 * count);
 
# Driver Code
 
# Given number N
N = 80;
 
# Function Call
findSolutions(N);
 
# This code is contributed by Code_Mech

// C# program for the above approach
using System;
class GFG{
 
// Function to find the integral
// solutions of the given equation
static void findSolutions(int N)
{
 
    // Initialise count to 0
    int count = 0;
 
    // Iterate till sqrt(N)
    for(int i = 1; i <= Math.Sqrt(N); i++)
    {
        if (N % i == 0)
        {
                 
            // If divisor's pair sum is even
            if ((i + N / i) % 2 == 0)
            {
                count++;
            }
        }
    }
     
    // Print the total possible solutions
    Console.Write(4 * count);
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given number N
    int N = 80;
     
    // Function Call
    findSolutions(N);
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// Javascript program for the above approach
 
// Function to find the integral
// solutions of the given equation
function findSolutions(N)
{
     
    // Initialise count to 0
    let count = 0;
 
    // Iterate till sqrt(N)
    for(let i = 1; i <= Math.sqrt(N); i++)
    {
        if (N % i == 0)
        {
             
            // If divisor's pair sum is even
            if ((i + parseInt(N / i)) % 2 == 0)
            {
                count++;
            }
        }
    }
     
    // Print the total possible solutions
    document.write(4 * count + "<br>");
}
 
// Driver Code
 
// Given number N
let N = 80;
 
// Function Call
findSolutions(N);
 
// This code is contributed by souravmahato348
 
</script>

Complejidad del tiempo: O(sqrt(N))