¡Definitivamente no he aprendido a fondo la teoría de los números!
Sin embargo, si está interesado en aprender suficiente teoría numérica para poder resolver los problemas de la competencia de programación, hay algunos temas que siguen apareciendo repetidamente: aprenda esos y debería estar listo, ya que de vez en cuando tiene que cubrir las brechas leyendo temas adicionales. Basado en editoriales.
La mayor parte de la teoría de números que necesitas de forma regular se basa en la aritmética modular. Aprende las propiedades de las relaciones de congruencia sobre lo que sucede cuando sumas y multiplicas. Lo siguiente que debe hacer es calcular el inverso multiplicativo modular. Este es el primer lugar donde tendrías que usar la teoría numérica “real”. Puede acercarse a esto a través del algoritmo euclidiano extendido, calculando el mayor divisor común (gcd). También hay muchos otros problemas basados en gcd, como la generación de enteros de la forma ax + por. Por lo tanto, debe internalizar las propiedades de gcd como la identidad de Bezout.
La segunda forma de generar inversiones modulares es a través del pequeño teorema de Fermat. Esto se basa en la estructura de grupo de enteros módulo a número primo. Ocasionalmente, tiene problemas en los que necesita tener alguna idea acerca de las propiedades teóricas del grupo de los grupos multiplicativos de enteros, por lo que ese es un tema que debe estudiar si realmente desea profundizar. Cuando el módulo no es primo, necesita el teorema de Euler, un poco más complicado, basado en la función totient de Euler. Hay muchos problemas en los que necesitas usar esta función, así que aprende sus propiedades.
- ¿Qué debo aprender para ser tan bueno como debería ser?
- ‘Ventas’ es una habilidad importante para un empresario. ¿Cómo aprendo?
- ¿Cuánto cuesta aprender a hablar otro idioma?
- ¿Cuáles son los mejores desafíos prácticos que puedo hacer para aprender sobre las redes de computadoras?
- ¿Dónde puedo aprender habilidades de escritura?
Para poder resolver la mayoría de los problemas en gcd y la función totient de Euler y así sucesivamente, tiene que hacer la factorización prima. Tenga una buena implementación eficiente de Sieve of Eratosthenes, y aprenda cómo calcular la factorización prima y la función eficiente de su uso.
Hay algunos otros temas basados en los que he visto problemas en varios concursos:
- Enteros sin cuadrados y función de Möbius
- Factoriales: la fórmula de Legendre y el teorema de Wilson.
- Coeficiente binomial: computación modular y teorema de Kummer
- Expresando enteros como suma de cuadrados: el teorema de Fermat sobre sumas de dos cuadrados, el teorema de tres cuadrados de Legendre, el teorema de cuatro cuadrados de Lagrange
- Combinando módulos múltiples usando el teorema del resto chino
Además de estos, debe estar familiarizado con las técnicas de combinatoria para poder hacer cosas como contar el número de factores, el principio de inclusión-exclusión para resolver algunos problemas relacionados con la función de paciente y módulos múltiples, la inducción matemática, etc. Además, muy a menudo, cuando está atascado en algún problema, ayuda poder generar la solución para los primeros números utilizando la fuerza bruta y verificar la existencia de alguna secuencia en la Enciclopedia en línea de secuencias de enteros (OEIS).
Entonces, si desea aprender en profundidad, comience a aprender estos temas en línea (Wikipedia es un gran recurso) o con un libro. Podrá ver un agujero de conejo de temas avanzados, así que vaya tan lejos como desee. Por supuesto, complemente la lectura con la resolución de problemas, ya que la implementación de muchos conceptos de teoría de números puede ser bastante complicada.
¡Buena suerte!