Dados dos números A y B , la tarea es encontrar el número mínimo que debe agregarse a A y B de modo que se minimice su MCM .
Ejemplos:
Entrada: A = 6, B = 10
Salida: 2
Explicación: Al sumar 2 a A y B, el valor se convierte en 8 y 12 respectivamente. MCM de 8 y 12 es 24, que es el mínimo MCM posible.Entrada: A = 5, B = 10
Salida: 0
Explicación:
10 ya es el MCM mínimo de ambos números dados.
Por lo tanto, el número mínimo agregado es 0.
Enfoque: La idea se basa en la fórmula generalizada de que el MCM de (A + x) y (B + x) es igual a (A + x)*(B + x) / MCD (A + x, B + x) . Se puede observar que el MCD de (A + x) y (B + x) es igual al MCD de (B – A) y (A + x) . Entonces, el mcd es un divisor de (B − A) .
Por lo tanto, iterar sobre todos los divisores de (B − A) y si A % M = B % M (si M es uno de los divisores), entonces el valor de X (se debe sumar el valor mínimo) es igual a M − A % M .
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 for finding all divisors // of a given number vector<int> getDivisors(int diff) { // Stores the divisors of the // number diff vector<int> divisor; for (int i = 1; i * i <= diff; i++) { // If diff is a perfect square if (i == diff / i) { divisor.push_back(i); continue; } // If i divides diff then // diff / i also a divisor if (diff % i == 0) { divisor.push_back(i); divisor.push_back(diff / i); } } // Return the divisors stored return divisor; } // Function to find smallest integer x // such that LCM of (A + X) and (B + X) // is minimized int findTheSmallestX(int a, int b) { int diff = b - a; // Find all the divisors of diff vector<int> divisor = getDivisors(diff); // Find LCM of a and b int lcm = (a * b) / __gcd(a, b); int ans = 0; for (int i = 0; i < (int)divisor.size(); i++) { // From equation x = M - a % M // here M = divisor[i] int x = (divisor[i] - (a % divisor[i])); // If already checked for x == 0 if (!x) continue; // Find the product int product = (b + x) * (a + x); // Find the GCD int tempGCD = __gcd(a + x, b + x); int tempLCM = product / tempGCD; // If current lcm is minimum // than previous lcm, update ans if (lcm > tempLCM) { ans = x; lcm = tempLCM; } } // Print the number added cout << ans; } // Driver Code int main() { // Given A & B int A = 6, B = 10; // Function Call findTheSmallestX(A, B); return 0; }
Java
// Java program for the // above approach import java.util.*; class GFG{ // Recursive function to // return gcd of a and b static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Function for finding all // divisors of a given number static int[] getDivisors(int diff) { // Stores the divisors of // the number diff Vector<Integer> divisor = new Vector<>() ; for (int i = 1; i * i <= diff; i++) { // If diff is a perfect // square if (i == diff / i) { divisor.add(i); continue; } // If i divides diff then // diff / i also a divisor if (diff % i == 0) { divisor.add(i); divisor.add(diff / i); } } int []ans = new int[divisor.size()]; int j = 0; for(int i: divisor) ans[j] = i; // Return the divisors // stored return ans; } // Function to find smallest integer // x such that LCM of (A + X) and // (B + X) is minimized static void findTheSmallestX(int a, int b) { int diff = b - a; // Find all the divisors // of diff int[] divisor = getDivisors(diff); // Find LCM of a and b int lcm = (a * b) / __gcd(a, b); int ans = 0; for (int i = 0; i <divisor.length; i++) { // From equation x = M - a % M // here M = divisor[i] int x = 0; if(divisor[i] != 0) x = (divisor[i] - (a % divisor[i])); // If already checked for // x == 0 if (x == 0) continue; // Find the product int product = (b + x) * (a + x); // Find the GCD int tempGCD = __gcd(a + x, b + x); int tempLCM = product / tempGCD; // If current lcm is // minimum than previous // lcm, update ans if (lcm > tempLCM) { ans = x; lcm = tempLCM; } } // Print the number // added System.out.print(ans); } // Driver Code public static void main(String[] args) { // Given A & B int A = 6, B = 10; // Function Call findTheSmallestX(A, B); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach from math import gcd # Function for finding all divisors # of a given number def getDivisors(diff): # Stores the divisors of the # number diff divisor = [] for i in range(1, diff): if i * i > diff: break # If diff is a perfect square if (i == diff // i): divisor.append(i) continue # If i divides diff then # diff / i also a divisor if (diff % i == 0): divisor.append(i) divisor.append(diff // i) # Return the divisors stored return divisor # Function to find smallest integer x # such that LCM of (A + X) and (B + X) # is minimized def findTheSmallestX(a, b): diff = b - a # Find all the divisors of diff divisor = getDivisors(diff) # Find LCM of a and b lcm = (a * b) // gcd(a, b) ans = 0 for i in range(len(divisor)): # From equation x = M - a % M # here M = divisor[i] x = (divisor[i] - (a % divisor[i])) # If already checked for x == 0 if (not x): continue # Find the product product = (b + x) * (a + x) # Find the GCD tempGCD = gcd(a + x, b + x) tempLCM = product // tempGCD # If current lcm is minimum # than previous lcm, update ans if (lcm > tempLCM): ans = x lcm = tempLCM # Print the number added print(ans) # Driver Code if __name__ == '__main__': # Given A & B A = 6 B = 10 # Function Call findTheSmallestX(A, B) # This code is contributed by mohit kumar 29
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Recursive function to // return gcd of a and b static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Function for finding all // divisors of a given number static int[] getDivisors(int diff) { // Stores the divisors of // the number diff List<int> divisor = new List<int>(); for(int i = 1; i * i <= diff; i++) { // If diff is a perfect // square if (i == diff / i) { divisor.Add(i); continue; } // If i divides diff then // diff / i also a divisor if (diff % i == 0) { divisor.Add(i); divisor.Add(diff / i); } } int []ans = new int[divisor.Count]; int j = 0; foreach(int i in divisor) ans[j] = i; // Return the divisors // stored return ans; } // Function to find smallest integer // x such that LCM of (A + X) and // (B + X) is minimized static void findTheSmallestX(int a, int b) { int diff = b - a; // Find all the divisors // of diff int[] divisor = getDivisors(diff); // Find LCM of a and b int lcm = (a * b) / __gcd(a, b); int ans = 0; for(int i = 0; i < divisor.Length; i++) { // From equation x = M - a % M // here M = divisor[i] int x = 0; if (divisor[i] != 0) x = (divisor[i] - (a % divisor[i])); // If already checked for // x == 0 if (x == 0) continue; // Find the product int product = (b + x) * (a + x); // Find the GCD int tempGCD = __gcd(a + x, b + x); int tempLCM = product / tempGCD; // If current lcm is // minimum than previous // lcm, update ans if (lcm > tempLCM) { ans = x; lcm = tempLCM; } } // Print the number // added Console.Write(ans); } // Driver Code public static void Main(String[] args) { // Given A & B int A = 6, B = 10; // Function Call findTheSmallestX(A, B); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program for the // above approach // Recursive function to // return gcd of a and b function __gcd(a,b) { return b == 0 ? a : __gcd(b, a % b); } // Function for finding all // divisors of a given number function getDivisors(diff) { // Stores the divisors of // the number diff let divisor = []; for (let i = 1; i * i <= diff; i++) { // If diff is a perfect // square if (i == diff / i) { divisor.push(i); continue; } // If i divides diff then // diff / i also a divisor if (diff % i == 0) { divisor.push(i); divisor.push(diff / i); } } let ans = new Array(divisor.length); let j = 0; for(let i=0;i< divisor.length;i++) ans[i] = divisor[i]; // Return the divisors // stored return ans; } // Function to find smallest integer // x such that LCM of (A + X) and // (B + X) is minimized function findTheSmallestX(a,b) { let diff = b - a; // Find all the divisors // of diff let divisor = getDivisors(diff); // Find LCM of a and b let lcm = (a * b) / __gcd(a, b); let ans = 0; for (let i = 0; i <divisor.length; i++) { // From equation x = M - a % M // here M = divisor[i] let x = 0; if(divisor[i] != 0) x = (divisor[i] - (a % divisor[i])); // If already checked for // x == 0 if (x == 0) continue; // Find the product let product = (b + x) * (a + x); // Find the GCD let tempGCD = __gcd(a + x, b + x); let tempLCM = product / tempGCD; // If current lcm is // minimum than previous // lcm, update ans if (lcm > tempLCM) { ans = x; lcm = tempLCM; } } // Print the number // added document.write(ans); } // Driver Code // Given A & B let A = 6, B = 10; // Function Call findTheSmallestX(A, B); // This code is contributed by patel2127 </script>
2
Complejidad de tiempo: O(sqrt(B – A))
Espacio auxiliar: O(max(A, B))
Publicación traducida automáticamente
Artículo escrito por reapedjuggler y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA