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 2 / (Y – N)
- Por lo tanto, se puede observar que, para tener un entero positivo X , el resto cuando N 2 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 2 + N para que N 2 /(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 2 % (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++
// 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
// 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
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA