Número mínimo de incrementos/decrementos necesarios para realizar en uno de los dos números dados para que no sean coprimos

Dados dos enteros positivos A y B , la tarea es encontrar el número mínimo de incrementos/decrementos necesarios para realizar en A o B para que ambos números no sean coprimos . Ejemplos: Entrada: A = 12, B = 3 Salida: 0 Explicación: Dado que 12 y 3 ya no son coprimos, el recuento mínimo … Continue reading «Número mínimo de incrementos/decrementos necesarios para realizar en uno de los dos números dados para que no sean coprimos»

Lema de Hensel

El lema de Hensel es un resultado que estipula las condiciones para que las raíces de los polinomios módulo potencias de números primos sean «elevadas» a raíces módulo potencias superiores. El método de elevación descrito en la prueba recuerda al método de Newton para resolver ecuaciones. Digamos que las ecuaciones del siguiente tipo deben ser … Continue reading «Lema de Hensel»

Complejidad temporal del algoritmo euclidiano

En este artículo, discutiremos la complejidad temporal del Algoritmo Euclidiano que es O(log(min(a, b)) y se logra. Algoritmo de Euclides : es un método eficiente para encontrar el MCD (máximo común divisor) de dos números enteros. La complejidad temporal de este algoritmo es O(log(min(a, b)) . Recursivamente se puede expresar como: gcd(a, b) = gcd(b, … Continue reading «Complejidad temporal del algoritmo euclidiano»

Cuente todos los valores posibles de K menores que Y tales que MCD(X, Y) = MCD(X+K, Y)

Dados dos enteros X e Y , la tarea es encontrar el número de enteros, K , tal que mcd(X, Y) sea igual a mcd(X+K, Y) , donde 0 < K <Y . Ejemplos: Entrada: X = 3, Y = 15 Salida: 4 Explicación: Todos los valores posibles de K son {0, 3, 6, 9} … Continue reading «Cuente todos los valores posibles de K menores que Y tales que MCD(X, Y) = MCD(X+K, Y)»

Minimice los pasos necesarios para igualar dos valores mediante la división repetida por cualquiera de sus factores primos que sea menor que M

Dados tres enteros positivos M , X e Y , la tarea es encontrar el número mínimo de operaciones requeridas para hacer que X e Y sean iguales de modo que en cada operación se divida X o Y por uno de sus factores primos menor que M . Si no es posible hacer que … Continue reading «Minimice los pasos necesarios para igualar dos valores mediante la división repetida por cualquiera de sus factores primos que sea menor que M»

Comprueba si todos los elementos se pueden hacer iguales al dividir con X e Y

Dada una array arr[] y dos enteros X e Y. La tarea es verificar si es posible hacer que todos los elementos sean iguales dividiéndolos con X e Y cualquier número de veces, incluido 0. Ejemplos:  Entrada: arr[] = {2, 4, 6, 8}, X = 2, Y = 3  Salida: Sí  2 -> 2  4 … Continue reading «Comprueba si todos los elementos se pueden hacer iguales al dividir con X e Y»

Modifique la array de modo que la array no contenga ningún divisor común que no sea 1

Dada una array arr[] que consta de N enteros y un entero X , la tarea es verificar si es posible modificar la array de modo que la array no contenga ningún divisor común que no sea 1 , dividiendo repetidamente cualquier elemento de array de la array por cualquiera de sus divisores d (d … Continue reading «Modifique la array de modo que la array no contenga ningún divisor común que no sea 1»

Control de calidad – Cuestionarios de ubicación | HCF | Pregunta 11

El producto de dos números es 4107. Si el HCF de estos números es 37, entonces el número mayor es: (A) 101 (B) 107 (C) 111 (D) 185 Respuesta: (C) Explicación: Sea los números requeridos ser 37x y 37y. Entonces, 37x * 37y = 4107 Entonces, x * y = 4107/(37*37) = 3. Los coprimos … Continue reading «Control de calidad – Cuestionarios de ubicación | HCF | Pregunta 11»

Maximizar GCD de una array por incrementos o decrementos por K

Dada una array arr[] que consta de N enteros positivos y un entero positivo K , la tarea es maximizar el GCD de la array arr[] aumentando o disminuyendo cualquier elemento de la array en K . Ejemplos: Entrada: arr[] = {3, 9, 15, 24}, K = 1 Salida: 4 Explicación: Realice las siguientes operaciones … Continue reading «Maximizar GCD de una array por incrementos o decrementos por K»

Cuente números que tienen GCD con N igual al número en sí

Dado un entero positivo N , la tarea es encontrar el número de enteros positivos cuyo MCD con el entero N dado es el número en sí. Ejemplos: Entrada: N = 5 Salida: 2 Explicación: Los siguientes son los números cuyo MCD con N es el número mismo: Número 1: MCD(1, 5) = 1. Número … Continue reading «Cuente números que tienen GCD con N igual al número en sí»