Cómo mejorar mis habilidades en teoría de números para programación competitiva

Answer 1

Mi primer consejo sería leer sobre los conceptos básicos de la teoría de números. No tiene que memorizarlos por completo ni comprender completamente las pruebas, pero debe saber de su existencia. Arriba de mi cabeza en este momento, ahora deberías:

• Aritmética modular: propiedades de operaciones de módulo, inversa modular, pequeño teorema de Fermat, teorema del resto chino.
• Factorización prima: Tamiz para encontrar números primos, algoritmo para encontrar factorización prima.
• Combinatoria: coeficientes binomiales, teorema binomial, números catalanes, funciones generadoras.
• Divisibilidad: Máximo común divisor, mínimo común múltiplo, función divisor.

Entonces, lo que creo que te hace mejorar tus habilidades es tratar de resolver problemas relacionados con la teoría de números y cuando te quedas estancado (o incluso si los resuelves), lee el editorial sobre las soluciones y de esa manera puedes aprender cómo resolver el problema. problema.
Ahora, lo que solía hacer cuando estaba entrenando era esperar un par de días después de haber leído la solución para implementar el problema sin mirar la solución nuevamente . De esta manera, me aseguraría de entenderlo completamente y de esa manera podría resolver problemas similares en el futuro.

Si aún no lo ha hecho, un buen lugar para buscar problemas es el archivo de teoría de números de Codeforces. Lo he ordenado por la cantidad de personas que han resuelto cada problema, lo que podría ser un buen indicador de su dificultad. Trate de encontrar un problema que sea desafiante para usted pero que no sea imposible de resolver después de pensarlo por un tiempo.

¡La mejor de las suertes!