Recuento de pares ordenados (X, Y) que satisfacen la ecuación 1/X + 1/Y = 1/N

Dado un número entero positivo N , la tarea es encontrar el número de pares ordenados (X, Y) donde tanto X como Y son números enteros positivos, de modo que satisfagan la ecuación 1/X + 1/Y = 1/N .

Ejemplos:

Entrada: N = 5 
Salida: 3 
Explicación: Solo 3 pares {(30,6), (10,10), (6,30)} satisfacen la ecuación dada.
 

Entrada: N = 360 
Salida: 105 
 

Enfoque: 
Siga los pasos para resolver el problema: 
 

• Resuelve para X usando la ecuación dada. 
   

1/X + 1/Y = 1/N 
=> 1/X = 1/N – 1/Y 
=> 1/X = (Y – N) / NY 
=> X = NY / (Y – N) 

X = [ NY / (S – N) ] * (1)

=> X = [ NY / (Y – N) ] * [1 – N/Y + N/Y]

=> X = [ NY / (Y – N) ] * [(Y-N)/Y + N/Y]

=> X = N + N ² / (Y – N)

• Por lo tanto, se puede observar que, para tener un entero positivo X , el resto cuando N ² se divide por (Y – N) debe ser 0 .
• Se puede observar que el valor mínimo de Y puede ser N + 1 (para que el denominador Y – N > 0) y el valor máximo de Y puede ser N ² + N para que N ² /(Y – N) siga siendo positivo entero ≥ 1 .
• Luego itere sobre los valores máximos y mínimos posibles de Y , y para cada valor de Y para el cual N ² % (Y – N) == 0 , incremente el conteo .
• Finalmente, devuelva el conteo como el número de pares ordenados.

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 number of ordered
// positive integer pairs (x,y) such
// that  they satisfy the equation
void solve(int n)
{
    // Initialize answer variable
    int ans = 0;
 
// Iterate over all possible values of y
    for (int y = n + 1; y <= n * n + n; y++) {
 
        // For valid x and y,
        // (n*n)%(y - n) has to be 0
        if ((n * n) % (y - n) == 0) {
 
            // Increment count of ordered pairs
            ans += 1;
        }
    }
 
    // Print the answer
    cout << ans;
}
 
// Driver Code
int main()
{
    int n = 5;
    // Function call
    solve(n);
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to find number of ordered
// positive integer pairs (x,y) such
// that they satisfy the equation
static void solve(int n)
{
     
    // Initialize answer variable
    int ans = 0;
 
    // Iterate over all possible values of y
    for(int y = n + 1; y <= n * n + n; y++)
    {
         
        // For valid x and y,
        // (n*n)%(y - n) has to be 0
        if ((n * n) % (y - n) == 0)
        {
             
            // Increment count of ordered pairs
            ans += 1;
        }
    }
 
    // Print the answer
    System.out.print(ans);
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 5;
     
    // Function call
    solve(n);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to find number of ordered
# positive integer pairs (x,y) such
# that they satisfy the equation
def solve(n):
 
    # Initialize answer variable
    ans = 0
 
    # Iterate over all possible values of y
    y = n + 1
    while(y <= n * n + n):
 
        # For valid x and y,
        # (n*n)%(y - n) has to be 0
        if ((n * n) % (y - n) == 0):
             
            # Increment count of ordered pairs
            ans += 1
 
        y += 1
 
    # Print the answer
    print(ans)
 
# Driver Code
n = 5
 
# Function call
solve(n)
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find number of ordered
// positive integer pairs (x,y) such
// that they satisfy the equation
static void solve(int n)
{
     
    // Initialize answer variable
    int ans = 0;
 
    // Iterate over all possible values of y
    for(int y = n + 1; y <= n * n + n; y++)
    {
         
        // For valid x and y,
        // (n*n)%(y - n) has to be 0
        if ((n * n) % (y - n) == 0)
        {
             
            // Increment count of ordered pairs
            ans += 1;
        }
    }
 
    // Print the answer
    Console.Write(ans);
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 5;
     
    // Function call
    solve(n);
}
}
 
// This code is contributed by Amit Katiyar

<script>
// javascript program for the above approach   
// Function to find number of ordered
    // positive integer pairs (x,y) such
    // that they satisfy the equation
    function solve(n) {
 
        // Initialize answer variable
        var ans = 0;
 
        // Iterate over all possible values of y
        for (y = n + 1; y <= n * n + n; y++) {
 
            // For valid x and y,
            // (n*n)%(y - n) has to be 0
            if ((n * n) % (y - n) == 0) {
 
                // Increment count of ordered pairs
                ans += 1;
            }
        }
 
        // Print the answer
        document.write(ans);
    }
 
    // Driver Code
     
        var n = 5;
 
        // Function call
        solve(n);
 
// This code contributed by umadevi9616
</script>

Producción: 
 

3

Complejidad temporal: O(N*N)
Espacio auxiliar: O(1)