Dado un número entero N y la suma de sus divisores. La tarea es encontrar la suma de los inversos de los divisores de N .
Ejemplos:
Entrada: N = 6, Suma = 12
Salida: 2.00
Los divisores de N son {1, 2, 3, 6} La
suma del inverso de los divisores es igual a (1/1 + 1/2 + 1/3 + 1/6) = 2,0
Entrada: N = 9, Suma = 13
Salida: 1,44
Enfoque ingenuo: calcule todos los divisores del número entero N dado . Luego calcula la suma del inverso de los divisores calculados. Este enfoque daría TLE cuando el valor de N es grande.
Complejidad de tiempo: O(sqrt(N))
Enfoque eficiente: Supongamos que el número N tiene K divisores, digamos d 1 , d 2 , …, d K . Se da que d 1 + d 2 + … + d K = Suma
La tarea es calcular (1 / d 1 ) + (1 / d 2 ) + … + (1 / d K ).
Multiplica y divide la ecuación anterior por N . La ecuación se convierte en [(N / d 1 ) + (N / d 2 ) + … + (N / d K )] / N
Ahora es fácil ver que N / d i representaría otro divisor de N para todo 1 ≤ yo ≤ K. El numerador es igual a la suma de los divisores. Por lo tanto, la suma de los inversos de los divisores es igual a Sum / N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to return the // sum of inverse of divisors double SumofInverseDivisors(int N, int Sum) { // Calculating the answer double ans = (double)(Sum)*1.0 / (double)(N); // Return the answer return ans; } // Driver code int main() { int N = 9; int Sum = 13; // Function call cout << setprecision(2) << fixed << SumofInverseDivisors(N, Sum); return 0; }
Java
// Java implementation of above approach import java.math.*; import java.io.*; class GFG { // Function to return the // sum of inverse of divisors static double SumofInverseDivisors(int N, int Sum) { // Calculating the answer double ans = (double)(Sum)*1.0 / (double)(N); // Return the answer return ans; } // Driver code public static void main (String[] args) { int N = 9; int Sum = 13; // Function call System.out.println (SumofInverseDivisors(N, Sum)); } } // This code is contributed by jit_t.
Python
# Python implementation of above approach # Function to return the # sum of inverse of divisors def SumofInverseDivisors( N, Sum): # Calculating the answer ans = float(Sum)*1.0 /float(N); # Return the answer return round(ans,2); # Driver code N = 9; Sum = 13; print SumofInverseDivisors(N, Sum); # This code is contributed by CrazyPro
C#
// C# implementation of above approach using System; class GFG { // Function to return the // sum of inverse of divisors static double SumofInverseDivisors(int N, int Sum) { // Calculating the answer double ans = (double)(Sum)*1.0 / (double)(N); // Return the answer return ans; } // Driver code static public void Main () { int N = 9; int Sum = 13; // Function call Console.Write(SumofInverseDivisors(N, Sum)); } } // This code is contributed by ajit
Javascript
<script> // JavaScript implementation of above approach // Function to return the // sum of inverse of divisors function SumofInverseDivisors(N, Sum) { // Calculating the answer let ans = (Sum)*1.0 / (N); // Return the answer return ans; } // Driver code let N = 9; let Sum = 13; // Function call document.write(SumofInverseDivisors(N, Sum).toFixed(2)); // This code is contributed by Surbhi Tyagi. </script>
1.44
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)