Categoría: GCD-LCM

Conteo de GCD distintos entre todas las subsecuencias no vacías de una array dada

Posted on by Rudeus Greyrat

Dada una array de enteros arr[] de tamaño N , la tarea es calcular el número total de máximos comunes divisores (MCD) distintos entre todas las subsecuencias no vacías de arr[] . Ejemplos: Entrada: arr[]={3,4,8} N=3 Salida: 4 Explicación: Las diferentes subsecuencias no vacías posibles son {3}, {4}, {8}, {3,4}, {4, 8}, {3,8}, {3,4,8} y … Continue reading «Conteo de GCD distintos entre todas las subsecuencias no vacías de una array dada»

Encontrar un triplete coprimo no transitivo en un rango

Posted on by Rudeus Greyrat

Dados L y R, encuentre un posible triplete no transitivo (a, b, c) tal que el par (a, b) sea coprimo y el par (b, c) sea coprimo pero (a, c) no lo sea co-principal Por ejemplo: (2, 5, 6) es un triplete no transitivo ya que el par (2, 5) es coprimo y el par … Continue reading «Encontrar un triplete coprimo no transitivo en un rango»

Sub-arreglo más largo con GCD máximo

Posted on by Rudeus Greyrat

Dada una array arr[] de longitud N , la tarea es encontrar la longitud de la sub-array más larga con el máximo valor de GCD posible. Ejemplos:   Entrada: arr[] = {1, 2, 2}  Salida: 2  Aquí todos los sub-arreglos posibles y allí los GCD son:  1) {1} -> 1  2) {2} -> 2  3) {2} … Continue reading «Sub-arreglo más largo con GCD máximo»

Cuente el número de subsecuencias con GCD 1

Posted on by Rudeus Greyrat

Dada una array de N números, la tarea es contar el número de subsecuencias que tienen gcd igual a 1.  Ejemplos:  Input: a[] = {3, 4, 8, 16} Output: 7 The subsequences are: {3, 4}, {3, 8}, {3, 16}, {3, 4, 8}, {3, 4, 16}, {3, 8, 16}, {3, 4, 8, 16} Input: a[] = … Continue reading «Cuente el número de subsecuencias con GCD 1»

Divisores comunes de N números

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros. La tarea es encontrar todos los divisores comunes de todos los N enteros. Ejemplos   Entrada: arr[] = {6, 90, 12, 18, 30, 18}  Salida: 1 2 3 6  Explicación:  MCD de todos los números es 6.  Ahora para encontrar todos los divisores de 6, tenemos  6 = 1 … Continue reading «Divisores comunes de N números»

Encuentre el par de suma mínima cuyo MCD es mayor que 1

Posted on by Rudeus Greyrat

Dados dos enteros positivos A y B, la tarea es encontrar dos enteros positivos tales que pertenezcan al rango [A, B], tal que su MCD sea mayor que 1 y su suma sea la mínima entre todos los pares posibles. Entrada: 2, 3 Salida: -1 Explicación: Claramente no existe ningún par para el cual mcd … Continue reading «Encuentre el par de suma mínima cuyo MCD es mayor que 1»

Compruebe si existe un subconjunto con suma 1 cuando cada elemento se multiplica por un número entero

Posted on by Rudeus Greyrat

Dada una array arr[] de números positivos. La tarea es verificar si existe algún subconjunto de cualquier tamaño tal que después de multiplicar cada elemento del subconjunto con cualquier número entero, dará la suma del subconjunto como 1.  Ejemplos: Entrada: arr[] = {12, 5, 9, 21} Salida: Verdadero Explicación: Elija los números 5 y 9. … Continue reading «Compruebe si existe un subconjunto con suma 1 cuando cada elemento se multiplica por un número entero»

Mínimo dividir por 2 operaciones requeridas para hacer que GCD sea impar para una array dada

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros positivos, la tarea es encontrar el número mínimo de operaciones requeridas para hacer que el GCD del elemento de la array sea impar de modo que en cada operación un elemento de la array se pueda dividir por 2 . Ejemplos: Entrada: arr[] = {4, 6} Salida: 1 … Continue reading «Mínimo dividir por 2 operaciones requeridas para hacer que GCD sea impar para una array dada»

Encuentre un entero X que sea divisor de todos excepto exactamente un elemento en una array

Posted on by Rudeus Greyrat

Dada una array de enteros. Encuentre un entero X que sea el divisor de todos excepto exactamente un elemento en la array dada. Nota : El MCD de todos los elementos no es 1.  Ejemplos:   Input : arr[] = {6, 18, 3, 12} Output : 6 6 is the divisor of all except 3. Input … Continue reading «Encuentre un entero X que sea divisor de todos excepto exactamente un elemento en una array»

Encuentre el valor de P y el inverso modular de Q módulo 998244353

Posted on by Rudeus Greyrat

Dados dos enteros P y Q, la tarea es encontrar el valor de P y el inverso modular de Q módulo 998244353. Eso es    Nota: P y Q son números enteros coprimos Ejemplos:  Entrada: P = 1, Q = 4 Salida: 748683265 Explicación: Consulte a continuación la explicación del ejemplo. Entrada: P = 1, … Continue reading «Encuentre el valor de P y el inverso modular de Q módulo 998244353»