Dado un entero C , la tarea es encontrar el valor mínimo posible de max(A, B) tal que LCM(A, B) = C .
Ejemplos:
Entrada: C = 6
Salida: 3
max(1, 6) = 6
max(2, 3) = 3
y min(6, 3) = 3
Entrada: C = 9
Salida: 9
Enfoque: un enfoque para resolver este problema es encontrar todos los factores del número dado usando el enfoque discutido en este artículo y luego encontrar el par (A, B) que satisface las condiciones dadas y tomar el mínimo general del máximo de estos . pares
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the LCM of a and b int lcm(int a, int b) { return (a / __gcd(a, b) * b); } // Function to return the minimized value int getMinValue(int c) { int ans = INT_MAX; // To find the factors for (int i = 1; i <= sqrt(c); i++) { // To check if i is a factor of c and // the minimum possible number // satisfying the given conditions if (c % i == 0 && lcm(i, c / i) == c) { // Update the answer ans = min(ans, max(i, c / i)); } } return ans; } // Driver code int main() { int c = 6; cout << getMinValue(c); return 0; }
Java
// Java implementation of the approach class Solution { // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to return the LCM of a and b static int lcm(int a, int b) { return (a / __gcd(a, b) * b); } // Function to return the minimized value static int getMinValue(int c) { int ans = Integer.MAX_VALUE; // To find the factors for (int i = 1; i <= Math.sqrt(c); i++) { // To check if i is a factor of c and // the minimum possible number // satisfying the given conditions if (c % i == 0 && lcm(i, c / i) == c) { // Update the answer ans = Math.min(ans, Math.max(i, c / i)); } } return ans; } // Driver code public static void main(String args[]) { int c = 6; System.out.println(getMinValue(c)); } } // This code is contributed by Arnab Kundu
Python3
# Python implementation of the approach import sys # Recursive function to return gcd of a and b def __gcd(a, b): # Everything divides 0 if (a == 0): return b; if (b == 0): return a; # base case if (a == b): return a; # a is greater if (a > b): return __gcd(a - b, b); return __gcd(a, b - a); # Function to return the LCM of a and b def lcm(a, b): return (a / __gcd(a, b) * b); # Function to return the minimized value def getMinValue(c): ans = sys.maxsize; # To find the factors for i in range(1, int(pow(c, 1/2)) + 1): # To check if i is a factor of c and # the minimum possible number # satisfying the given conditions if (c % i == 0 and lcm(i, c / i) == c): # Update the answer ans = min(ans, max(i, c / i)); return int(ans); # Driver code if __name__ == '__main__': c = 6; print(getMinValue(c)); # This code is contributed by 29AjayKumar
C#
// C# implementation of the approach using System; class GFG { // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to return the LCM of a and b static int lcm(int a, int b) { return (a / __gcd(a, b) * b); } // Function to return the minimized value static int getMinValue(int c) { int ans = int.MaxValue; // To find the factors for (int i = 1; i <= Math.Sqrt(c); i++) { // To check if i is a factor of c and // the minimum possible number // satisfying the given conditions if (c % i == 0 && lcm(i, c / i) == c) { // Update the answer ans = Math.Min(ans, Math.Max(i, c / i)); } } return ans; } // Driver code public static void Main() { int c = 6; Console.WriteLine(getMinValue(c)); } } // This code is contributed by AnkitRai01
Javascript
<script> // javascript implementation of the approach // Recursive function to return gcd of a and b function __gcd(a , b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to return the LCM of a and b function lcm(a , b) { return (a / __gcd(a, b) * b); } // Function to return the minimized value function getMinValue(c) { var ans = Number.MAX_VALUE; // To find the factors for (i = 1; i <= Math.sqrt(c); i++) { // To check if i is a factor of c and // the minimum possible number // satisfying the given conditions if (c % i == 0 && lcm(i, c / i) == c) { // Update the answer ans = Math.min(ans, Math.max(i, c / i)); } } return ans; } // Driver code var c = 6; document.write(getMinValue(c)); // This code contributed by shikhasingrajput </script>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA