Introducción a la Función de Euler
La función de Euler, denotada como φ(n), cuenta el número de enteros positivos menores o iguales a n que son coprimos con n. Dos enteros a y b son coprimos si su máximo común divisor (MCD) es 1.
Fórmula de la Función de Euler
Si la factorización prima de n es n = p₁c₁ ⋅ p₂c₂ ⋅ ... ⋅ pmcm, entonces la función de Euler se calcula como:
φ(n) = n ⋅ ...
Publicado el 6-19 22:10
Análisis de Problemas de ICPC 2023 Hangzhou (B, D, E, F, G, H, J, M)
El concurso ICPC 2023 Hangzhou presentó una cantidad generosa de medallas de oro, pero el umbral para obtener una se centró en la resolución de cinco problemas. Más allá de ese punto, todos los problemas restantes fueron considerados de nivel de medalla de oro, con cuatro de ellos (A, B, E, F) siendo accesibles para la mayoría de los competidor ...
Publicado el 6-18 07:13
Verificación de Primalidad y Descomposición en Factores Primos
División por Prueba
Este enfoque consiste en probar todos los enteros desde 2 hasta la raíz cuadrada de n para determinar si es primo. Tiene una complejidad de O(√n) y es viable para n ≤ 1014. Una optimización común es iterar solo sobre números primos, aunque la precomputación de estos puede consumir tiempo adicional.
Test de Miller-Rabin
Es un ...
Publicado el 6-1 14:03