La función Totient de Euler Φ(n) para una entrada n es el recuento de números en {1, 2, 3, …, n} que son primos relativos a n, es decir, los números cuyo MCD (máximo común divisor) con n es 1 . Por ejemplo, Φ(4) = 2, Φ(3) = 2 y Φ(5) = 4. Hay 2 … Continue reading «Función Totient de Euler para todos los números menores o iguales que n»
Dados dos enteros A y B , la tarea es calcular 2 2A % B . Ejemplos: Entrada: A = 3, B = 5 Salida: 1 2 23 % 5 = 2 8 % 5 = 256 % 5 = 1. Entrada: A = 10, B = 13 Salida: 3 Enfoque: el problema se puede … Continue reading «Encuentre 2^(2^A) % B»
Considere el siguiente método simple para multiplicar dos números. C // A Simple solution that causes overflow when // value of (a % mod) * (b % mod) becomes more than // maximum value of long long int #define ll long long ll multiply(ll a, ll b, ll mod) { return ((a % mod) … Continue reading «¿Cómo evitar el desbordamiento en la multiplicación modular?»
Dado un número ‘n’ y un primo ‘p’, encuentre la raíz cuadrada de n bajo módulo p si existe. Ejemplos: Input: n = 2, p = 113 Output: 62 62^2 = 3844 and 3844 % 113 = 2 Input: n = 2, p = 7 Output: 3 or 4 3 and 4 both are square roots … Continue reading «Buscar raíz cuadrada en Módulo p | Conjunto 2 (algoritmo Shanks Tonelli)»
Dada una string que consta de dígitos 0-9, cuente el número de subsecuencias en ella divisible por m. Ejemplos: Input : str = «1234», n = 4 Output : 4 The subsequences 4, 12, 24 and 124 are divisible by 4. Input : str = «330», n = 6 Output : 4 The subsequences 30, … Continue reading «Número de subsecuencias en una string divisible por n»
Dado un arreglo arr[] que consta de N enteros positivos, la tarea es encontrar el valor máximo de ∑(M mod arr[i]) , donde arr[i] es cualquier elemento del arreglo, para un entero no negativo M . Ejemplos: Entrada: arr[] = {3, 4, 6} Salida: 10 Explicación: Para M = 11, (11 mod 3) + (11 … Continue reading «Maximizar Modulo Sum posible desde una array»
Dado un número entero N y un número entero F N que denota el N- ésimo término de la ecuación lineal F(N) = (2 * F(N – 1)) % M , donde M es 10 9 + 7 , la tarea es encontrar el valor de F(1) . Ejemplos: Entrada: N = 2, F N … Continue reading «Primer término del enésimo término dado de la ecuación F(N) = (2 * F(N – 1)) % 10^9 + 7»
Dado un número ‘n’, escriba una función que imprima el último dígito del n’th (‘n’ también puede ser un número grande) número de Fibonacci. Ejemplos: Input : n = 0 Output : 0 Input: n = 2 Output : 1 Input : n = 7 Output : 3 Método 1: (Método ingenuo) El enfoque simple es … Continue reading «Programa para encontrar el último dígito del enésimo número de Fibonacci»
Dada una array arr[] de longitud N y un entero positivo M , la tarea es encontrar el XOR bit a bit de todos los elementos de la array cuyo inverso modular con M existe. Ejemplos: Entrada: arr[] = {1, 2, 3}, M = 4 Salida: 2 Explicación: Inicialice el valor xor con 0: para … Continue reading «XOR de elementos de array cuyo inverso modular con un número dado existe»
A continuación se presentan algunas propiedades interesantes de la adición modular: (a + b) mod m = ((a mod m) + (b mod m)) mod m (a + b + c) mod m = ((a mod m) + (b mod m) + (c mod m )) modelo m Ejemplo 1: Hallar el resto de 22 … Continue reading «Adición modular»