reference.tex

\documentclass[11pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage[spanish]{babel}
\decimalpoint
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage[margin=0.6in,landscape]{geometry}
\usepackage{fancyhdr}
\usepackage[inline]{enumitem}
\usepackage{float}
\usepackage{cancel}
\usepackage{bigints}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{listingsutf8}
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{apacite}
\usepackage{minted}
\usepackage{tcolorbox}
\usepackage{multicol}
\usepackage{hyperref}
\hypersetup{
	colorlinks,
	citecolor=black,
	filecolor=black,
	linkcolor=black,
	urlcolor=black
}
\twocolumn
\usepackage{tipa}
\pagestyle{fancy}
\newcommand{\xvdash}[1]{%
	\vdash^{\mkern-10mu\scriptscriptstyle\rule[-.9ex]{0pt}{0pt}#1}%
}
\setlength{\headheight}{15pt} 
\lhead{Reference}
\rhead{\thepage}
\lfoot{ESCOM-IPN}
\renewcommand{\footrulewidth}{0.5pt}
\setlength{\parskip}{0.5em}
\newcommand{\ve}[1]{\overrightarrow{#1}}
\newcommand{\abs}[1]{\left\lvert #1 \right\lvert}
\newcommand{\blank}{\text{\textcrb}}
\title{Reference}

\lstdefinestyle{customc}{
	belowcaptionskip=1\baselineskip,
	breaklines=true,
	frame=L,
	xleftmargin=\parindent,
	language=C++,
	showstringspaces=false,
	basicstyle=\ttfamily,
	keywordstyle=\bfseries\color{green!40!black},
	commentstyle=\itshape\color{purple!40!black},
	identifierstyle=\color{blue},
	numbers=left,
	stringstyle=\color{orange},
}
\newcommand{\genstirlingI}[3]{%
	\genfrac{[}{]}{0pt}{#1}{#2}{#3}%
}
\newcommand{\genstirlingII}[3]{%
	\genfrac{\{}{\}}{0pt}{#1}{#2}{#3}%
}
\newcommand{\genEuler}[3]{%
	\genfrac{<}{>}{0pt}{#1}{#2}{#3}%
}
\newcommand{\stirlingI}[2]{\genstirlingI{}{#1}{#2}}
\newcommand{\stirlingII}[2]{\genstirlingII{}{#1}{#2}}
\newcommand{\euler}[2]{\genEuler{}{#1}{#2}}

\begin{document}
	\tableofcontents
	
	\clearpage
	\section{Teoría de números}
		\subsection{Funciones básicas}
			\subsubsection{Función piso y techo}
			\inputminted[tabsize=2,breaklines,firstline=5,lastline=21,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Exponenciación y multiplicación binaria}
			\inputminted[tabsize=2,breaklines,firstline=23,lastline=46,fontsize=\small]{c++}{numberTheory.cpp}
			\inputminted[tabsize=2,breaklines,firstline=1041,lastline=1047,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Mínimo común múltiplo y máximo común divisor}
			\inputminted[tabsize=2,breaklines,firstline=48,lastline=68,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Euclides extendido e inverso modular}
			\inputminted[tabsize=2,breaklines,firstline=70,lastline=85,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Todos los inversos módulo $p$}
			\inputminted[tabsize=2,breaklines,firstline=711,lastline=718,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Exponenciación binaria modular}
			\inputminted[tabsize=2,breaklines,firstline=93,lastline=106,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Teorema chino del residuo}
			\inputminted[tabsize=2,breaklines,firstline=950,lastline=964,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Coeficiente binomial}
			\inputminted[tabsize=2,breaklines,firstline=433,lastline=440,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Fibonacci}
			\inputminted[tabsize=2,breaklines,firstline=720,lastline=741,fontsize=\small]{c++}{numberTheory.cpp}
		
		\subsection{Cribas}
			\subsubsection{Criba de divisores}
			\inputminted[tabsize=2,breaklines,firstline=119,lastline=130,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Criba de primos}
			\inputminted[tabsize=2,breaklines,firstline=132,lastline=146,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Criba de factor primo más pequeño}
			\inputminted[tabsize=2,breaklines,firstline=150,lastline=159,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Criba de factor primo más grande}
			\inputminted[tabsize=2,breaklines,firstline=939,lastline=947,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Criba de factores primos}
			\inputminted[tabsize=2,breaklines,firstline=162,lastline=170,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Criba de la función $\varphi$ de Euler}
			\inputminted[tabsize=2,breaklines,firstline=172,lastline=180,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Criba de la función $\mu$}
			\inputminted[tabsize=2,breaklines,firstline=801,lastline=809,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Triángulo de Pascal}
			\inputminted[tabsize=2,breaklines,firstline=182,lastline=192,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Segmented sieve}
			\inputminted[tabsize=2,breaklines,firstline=860,lastline=892,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Criba de primos lineal}
			\inputminted[tabsize=2,breaklines,firstline=811,lastline=825,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Criba lineal para funciones multiplicativas}
			\inputminted[tabsize=2,breaklines,firstline=827,lastline=858,fontsize=\small]{c++}{numberTheory.cpp}
			
		
		\subsection{Factorización}
			\subsubsection{Factorización de un número}
			\inputminted[tabsize=2,breaklines,firstline=194,lastline=207,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Potencia de un primo que divide a un factorial}
			\inputminted[tabsize=2,breaklines,firstline=418,lastline=422,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Factorización de un factorial}
			\inputminted[tabsize=2,breaklines,firstline=424,lastline=431,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Factorial módulo $p$}
			\inputminted[tabsize=2,breaklines,firstline=1024,lastline=1039,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Factorización usando Pollard-Rho}
			\inputminted[tabsize=2,breaklines,firstline=657,lastline=709,fontsize=\small]{c++}{numberTheory.cpp}
		
		\subsection{Funciones aritméticas famosas}
			\subsubsection{Función $\sigma$}
			\inputminted[tabsize=2,breaklines,firstline=209,lastline=226,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Función $\Omega$}
			\inputminted[tabsize=2,breaklines,firstline=228,lastline=235,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Función $\omega$}
			\inputminted[tabsize=2,breaklines,firstline=237,lastline=244,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Función $\varphi$ de Euler}
			\inputminted[tabsize=2,breaklines,firstline=251,lastline=258,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Función $\mu$}
			\inputminted[tabsize=2,breaklines,firstline=276,lastline=287,fontsize=\small]{c++}{numberTheory.cpp}
			
		\subsection{Orden multiplicativo, raíces primitivas y raíces de la unidad}
			\subsubsection{Función $\lambda$ de Carmichael}
			\inputminted[tabsize=2,breaklines,firstline=260,lastline=274,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Orden multiplicativo módulo $m$}
			\inputminted[tabsize=2,breaklines,firstline=289,lastline=302,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Número de raíces primitivas (generadores) módulo $m$}
			\inputminted[tabsize=2,breaklines,firstline=307,lastline=313,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Test individual de raíz primitiva módulo $m$}
			\inputminted[tabsize=2,breaklines,firstline=315,lastline=325,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Test individual de raíz $k$-ésima de la unidad módulo $m$}
			\inputminted[tabsize=2,breaklines,firstline=327,lastline=336,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Encontrar la primera raíz primitiva módulo $m$}
			\inputminted[tabsize=2,breaklines,firstline=338,lastline=355,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Encontrar la primera raíz $k$-ésima de la unidad módulo $m$}
			\inputminted[tabsize=2,breaklines,firstline=357,lastline=373,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Logaritmo discreto}
			\inputminted[tabsize=2,breaklines,firstline=375,lastline=398,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Raíz $k$-ésima discreta}
			\inputminted[tabsize=2,breaklines,firstline=400,lastline=416,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Algoritmo de Tonelli-Shanks para raíces cuadradas módulo $p$}
			\inputminted[tabsize=2,breaklines,firstline=908,lastline=937,fontsize=\small]{c++}{numberTheory.cpp}
			
		\subsection{Particiones}
			\subsubsection{Función $P$ (particiones de un entero positivo)}
			\inputminted[tabsize=2,breaklines,firstline=519,lastline=547,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Función $Q$ (particiones de un entero positivo en distintos sumandos)}
			\inputminted[tabsize=2,breaklines,firstline=549,lastline=596,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Número de factorizaciones ordenadas}
			\inputminted[tabsize=2,breaklines,firstline=743,lastline=771,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Número de factorizaciones no ordenadas}
			\inputminted[tabsize=2,breaklines,firstline=773,lastline=799,fontsize=\small]{c++}{numberTheory.cpp}
			
		\subsection{Otros}
			\subsubsection{Cambio de base}
			\inputminted[tabsize=2,breaklines,firstline=442,lastline=462,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Fracciones continuas}
			\inputminted[tabsize=2,breaklines,firstline=598,lastline=640,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Ecuación de Pell}
			\inputminted[tabsize=2,breaklines,firstline=642,lastline=655,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Números de Bell}
			\inputminted[tabsize=2,breaklines,firstline=894,lastline=906,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Números de Stirling}
			\inputminted[tabsize=2,breaklines,firstline=967,lastline=988,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Números de Euler}
			\inputminted[tabsize=2,breaklines,firstline=990,lastline=1001,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Prime counting function in $O(n^{3/4}/\ln(n))$}
			\inputminted[tabsize=2,breaklines,firstline=33,lastline=91,fontsize=\small]{c++}{pi.cpp}
			
			\subsubsection{Suma de función multiplicativa general}
			\inputminted[tabsize=2,breaklines,firstline=164,lastline=185,fontsize=\small]{c++}{pi.cpp}
			
			\subsubsection{Powerful sieve}
			\inputminted[tabsize=2,breaklines,firstline=187,lastline=206,fontsize=\small]{c++}{pi.cpp}
			
			\subsubsection{Suma de la función piso}
			\inputminted[tabsize=2,breaklines,firstline=1003,lastline=1010,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Periodo de Pisano}
			\inputminted[tabsize=2,breaklines,firstline=1049,lastline=1076,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Suma en dos cuadrados de un primo}
			\inputminted[tabsize=2,breaklines,firstline=1098,lastline=1117,fontsize=\small]{c++}{numberTheory.cpp}
			
			\subsubsection{Polinomio ciclotómico}
			\inputminted[tabsize=2,breaklines,firstline=1078,lastline=1096,fontsize=\small]{c++}{numberTheory.cpp}
			
	\newpage
	\section{Números racionales}
		\subsection{Estructura \texttt{fraccion}}
		\inputminted[tabsize=2,breaklines,firstline=7,lastline=123,fontsize=\small]{c++}{fraccion.cpp}
		
	\newpage
	\section{Álgebra lineal}
		\subsection{Estructura \texttt{matrix}}
		\inputminted[tabsize=2,breaklines,firstline=7,lastline=130,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Transpuesta y traza}
		\inputminted[tabsize=2,breaklines,firstline=132,lastline=145,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Gauss Jordan}
		\inputminted[tabsize=2,breaklines,firstline=147,lastline=190,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Matriz escalonada por filas y reducida por filas}
		\inputminted[tabsize=2,breaklines,firstline=192,lastline=202,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Matriz inversa}
		\inputminted[tabsize=2,breaklines,firstline=204,lastline=225,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Determinante}
		\inputminted[tabsize=2,breaklines,firstline=227,lastline=240,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Matriz de cofactores y adjunta}
		\inputminted[tabsize=2,breaklines,firstline=242,lastline=267,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Factorización $PA=LU$}
		\inputminted[tabsize=2,breaklines,firstline=269,lastline=285,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Polinomio característico}
		\inputminted[tabsize=2,breaklines,firstline=287,lastline=297,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Gram-Schmidt}
		\inputminted[tabsize=2,breaklines,firstline=299,lastline=315,fontsize=\small]{c++}{matrix.cpp}
		
		\subsection{Recurrencias lineales}
		\inputminted[tabsize=2,breaklines,firstline=7,lastline=33,fontsize=\small]{c++}{recurrence.cpp}
		
		\subsection{Berlekamp-Massey}
		\inputminted[tabsize=2,breaklines,firstline=46,lastline=81,fontsize=\small]{c++}{recurrence.cpp}
		
		\subsection{Simplex}
		\inputminted[tabsize=2,breaklines,fontsize=\small]{c++}{simplex.cpp}
		
		
	\newpage
	\section{FFT}
		\subsection{Declaraciones previas}
		\inputminted[tabsize=2,breaklines,firstline=3,lastline=11,fontsize=\small]{c++}{fft.cpp}
		
		\subsection{FFT con raíces de la unidad complejas}
		\inputminted[tabsize=2,breaklines,firstline=13,lastline=34,fontsize=\small]{c++}{fft.cpp}
		
		\subsection{FFT con raíces de la unidad en $\mathbb{Z}_p$ (NTT)}
		\inputminted[tabsize=2,breaklines,firstline=36,lastline=73,fontsize=\small]{c++}{fft.cpp}
			\subsubsection{Valores para escoger el generador y el módulo}
				\begin{table}[H]
					\centering
					\begin{tabular}{|p{2.3cm}|p{2.7cm}|p{4.5cm}|}
						\hline
						Generador ($g$) & Tamaño máximo del arreglo ($n$) & Módulo $p$ \\ \hline
						3 & $2^{16}$ & $1 \times 2^{16} + 1 = 65537$ \\ \hline
						10 & $2^{18}$ & $3 \times 2^{18} + 1 = 786433$ \\ \hline
						3 & $2^{19}$ & $11 \times 2^{19} + 1 = 5767169$ \\ \hline
						\textbf{3} & $\mathbf{2^{20}}$ & $7 \times 2^{20} + 1 = \textbf{7340033}$ \\ \hline
						3 & $2^{21}$ & $11 \times 2^{21} + 1 = 23068673$ \\ \hline
						3 & $2^{22}$ & $25 \times 2^{22} + 1 = 104857601$ \\ \hline
						3 & $2^{22}$ & $235 \times 2^{22} + 1 = 985661441$ \\ \hline
						26 & $2^{23}$ & $105 \times 2^{23} + 1 = 880803841$ \\ \hline
						\textbf{3} & $\mathbf{2^{23}}$ & $119 \times 2^{23} + 1 = \textbf{998244353}$ \\ \hline
						11 & $2^{24}$ & $45 \times 2^{24} + 1 = 754974721$ \\ \hline
						3 & $2^{25}$ & $5 \times 2^{25} + 1 = 167772161$ \\ \hline
						3 & $2^{26}$ & $7 \times 2^{26} + 1 = 469762049$ \\ \hline
						31 & $2^{27}$ & $15 \times 2^{27} + 1 = 2013265921$ \\ \hline
					\end{tabular}
				\end{table}
			
		\subsection{Multiplicación de polinomios (convolución lineal)}
		\inputminted[tabsize=2,breaklines,firstline=75,lastline=100,fontsize=\small]{c++}{fft.cpp}
		
		\subsection{Aplicaciones}
			\subsubsection{Multiplicación de números enteros grandes}
			\inputminted[tabsize=2,breaklines,firstline=102,lastline=135,fontsize=\small]{c++}{fft.cpp}
			
			\subsubsection{Inverso multiplicativo de un polinomio}
			\inputminted[tabsize=2,breaklines,firstline=137,lastline=158,fontsize=\small]{c++}{fft.cpp}
			
			\subsubsection{Raíz cuadrada de un polinomio}
			\inputminted[tabsize=2,breaklines,firstline=160,lastline=181,fontsize=\small]{c++}{fft.cpp}
			
			\subsubsection{Logaritmo y exponencial de un polinomio}
			\inputminted[tabsize=2,breaklines,firstline=183,lastline=225,fontsize=\small]{c++}{fft.cpp}
			
			\subsubsection{Cociente y residuo de dos polinomios}
			\inputminted[tabsize=2,breaklines,firstline=227,lastline=252,fontsize=\small]{c++}{fft.cpp}
			
			\subsubsection{Multievaluación rápida}
			\inputminted[tabsize=2,breaklines,firstline=254,lastline=294,fontsize=\small]{c++}{fft.cpp}
			
			\subsubsection{Interpolación}
			\inputminted[tabsize=2,breaklines,firstline=296,lastline=320,fontsize=\small]{c++}{fft.cpp}
			
			\subsubsection{Half GCD}
			\inputminted[tabsize=2,breaklines,firstline=322,lastline=397,fontsize=\small]{c++}{fft.cpp}
			
			\subsubsection{DFT con tamaño de vector arbitrario (algoritmo de Bluestein)}
			\inputminted[tabsize=2,breaklines,firstline=399,lastline=419,fontsize=\small]{c++}{fft.cpp}
			
		\subsection{Convolución de dos vectores reales con solo dos FFT's}
		\inputminted[tabsize=2,breaklines,firstline=421,lastline=441,fontsize=\small]{c++}{fft.cpp}
			
		\subsection{Convolución con módulo arbitrario}
		\inputminted[tabsize=2,breaklines,firstline=443,lastline=500,fontsize=\small]{c++}{fft.cpp}
		
		\subsection{Transformada rápida de Walsh–Hadamard}
		\inputminted[tabsize=2,breaklines,firstline=502,lastline=533,fontsize=\small]{c++}{fft.cpp}
			
	\newpage
	\section{Geometría}
		\subsection{Estructura \texttt{point}}
		\inputminted[tabsize=2,breaklines,firstline=3,lastline=60,fontsize=\small]{c++}{geometry.cpp}
		
		\subsection{Líneas y segmentos}
			\subsubsection{Verificar si un punto pertenece a una línea o segmento}
			\inputminted[tabsize=2,breaklines,firstline=62,lastline=70,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Intersección de líneas}
			\inputminted[tabsize=2,breaklines,firstline=72,lastline=91,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Intersección línea-segmento}
			\inputminted[tabsize=2,breaklines,firstline=93,lastline=106,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Intersección de segmentos}
			\inputminted[tabsize=2,breaklines,firstline=108,lastline=125,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Distancia punto-recta}
			\inputminted[tabsize=2,breaklines,firstline=127,lastline=130,fontsize=\small]{c++}{geometry.cpp}
			
		\subsection{Polígonos}
			\subsubsection{Perímetro y área de un polígono}
			\inputminted[tabsize=2,breaklines,firstline=132,lastline=148,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Envolvente convexa (convex hull) de un polígono}
			\inputminted[tabsize=2,breaklines,firstline=150,lastline=169,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Verificar si un punto está en el perímetro o dentro de un polígono}
			\inputminted[tabsize=2,breaklines,firstline=171,lastline=195,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Verificar si un punto pertenece a un polígono convexo $O(\log n)$}
			\inputminted[tabsize=2,breaklines,firstline=197,lastline=220,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Cortar un polígono con una recta}
			\inputminted[tabsize=2,breaklines,firstline=226,lastline=242,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Centroide de un polígono}
			\inputminted[tabsize=2,breaklines,firstline=259,lastline=269,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Pares de puntos antipodales}
			\inputminted[tabsize=2,breaklines,firstline=271,lastline=282,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Diámetro y ancho}
			\inputminted[tabsize=2,breaklines,firstline=284,lastline=298,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Smallest enclosing rectangle}
			\inputminted[tabsize=2,breaklines,firstline=300,lastline=319,fontsize=\small]{c++}{geometry.cpp}
		
		\subsection{Círculos}
			\subsubsection{Distancia punto-círculo}
			\inputminted[tabsize=2,breaklines,firstline=321,lastline=324,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Proyección punto exterior a círculo}
			\inputminted[tabsize=2,breaklines,firstline=326,lastline=329,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Puntos de tangencia desde punto exterior}
			\inputminted[tabsize=2,breaklines,firstline=331,lastline=337,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Intersección línea-círculo y segmento-círculo}
			\inputminted[tabsize=2,breaklines,firstline=339,lastline=349,fontsize=\small]{c++}{geometry.cpp}
			\inputminted[tabsize=2,breaklines,firstline=351,lastline=358,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Centro y radio a través de tres puntos}
			\inputminted[tabsize=2,breaklines,firstline=360,lastline=365,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Intersección de círculos}
			\inputminted[tabsize=2,breaklines,firstline=367,lastline=382,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Contención de círculos}
			\inputminted[tabsize=2,breaklines,firstline=384,lastline=403,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Tangentes comunes externas e internas}
			\inputminted[tabsize=2,breaklines,firstline=405,lastline=417,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Intersección polígono-círculo}
			\inputminted[tabsize=2,breaklines,firstline=419,lastline=454,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Smallest enclosing circle}
			\inputminted[tabsize=2,breaklines,firstline=456,lastline=487,fontsize=\small]{c++}{geometry.cpp}
			
			\subsubsection{Área de unión de círculos}
			\inputminted[tabsize=2,breaklines,firstline=773,lastline=845,fontsize=\small]{c++}{geometry.cpp}
		
		\subsection{Par de puntos más cercanos}
		\inputminted[tabsize=2,breaklines,firstline=489,lastline=515,fontsize=\small]{c++}{geometry.cpp}
		
		\subsection{Vantage Point Tree (puntos más cercanos a cada punto)}
		\inputminted[tabsize=2,breaklines,firstline=517,lastline=580,fontsize=\small]{c++}{geometry.cpp}
		
		\subsection{Suma Minkowski}
		\inputminted[tabsize=2,breaklines,firstline=582,lastline=603,fontsize=\small]{c++}{geometry.cpp}
		
		\subsection{Triangulación de Delaunay}
		\inputminted[tabsize=2,breaklines,firstline=605,lastline=771,fontsize=\small]{c++}{geometry.cpp}
		
		\subsection{Half plane intersection}
		\inputminted[tabsize=2,breaklines,firstline=847,lastline=920,fontsize=\small]{c++}{geometry.cpp}
		
	\newpage
	\section{Grafos}
		\subsection{Disjoint Set}
		\inputminted[tabsize=2,breaklines,firstline=8,lastline=37,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Definiciones}
		\inputminted[tabsize=2,breaklines,firstline=39,lastline=100,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{DFS genérica}
		\inputminted[tabsize=2,breaklines,firstline=411,lastline=429,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Dijkstra}
		\inputminted[tabsize=2,breaklines,firstline=102,lastline=125,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Bellman Ford}
		\inputminted[tabsize=2,breaklines,firstline=127,lastline=161,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Floyd}
		\inputminted[tabsize=2,breaklines,firstline=167,lastline=175,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Cerradura transitiva $O(V^3)$}
		\inputminted[tabsize=2,breaklines,firstline=177,lastline=184,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Cerradura transitiva $O(V^2)$}
		\inputminted[tabsize=2,breaklines,firstline=186,lastline=200,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Verificar si el grafo es bipartito}
		\inputminted[tabsize=2,breaklines,firstline=202,lastline=224,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Orden topológico}
		\inputminted[tabsize=2,breaklines,firstline=226,lastline=252,fontsize=\small]{c++}{graph.cpp}

		\subsection{Detectar ciclos}
		\inputminted[tabsize=2,breaklines,firstline=254,lastline=274,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Puentes y puntos de articulación}
		\inputminted[tabsize=2,breaklines,firstline=276,lastline=304,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Componentes fuertemente conexas}
		\inputminted[tabsize=2,breaklines,firstline=306,lastline=335,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Árbol mínimo de expansión (Kruskal)}
		\inputminted[tabsize=2,breaklines,firstline=337,lastline=353,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Máximo emparejamiento bipartito}
		\inputminted[tabsize=2,breaklines,firstline=355,lastline=409,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Circuito euleriano}
		
		
	\newpage
	\section{Árboles}		
		\subsection{Estructura \texttt{tree}}
		\inputminted[tabsize=2,breaklines,firstline=432,lastline=470,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{$k$-ésimo ancestro}
		\inputminted[tabsize=2,breaklines,firstline=472,lastline=484,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{LCA}
		\inputminted[tabsize=2,breaklines,firstline=486,lastline=505,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Distancia entre dos nodos}
		\inputminted[tabsize=2,breaklines,firstline=507,lastline=530,fontsize=\small]{c++}{graph.cpp}
		
		\subsection{Link Cut}
		
		
	\newpage
	\section{Flujos}
		\subsection{Estructura \texttt{flowEdge}}
		\inputminted[tabsize=2,breaklines,firstline=4,lastline=17,fontsize=\small]{c++}{flow.cpp}
		
		\subsection{Estructura \texttt{flowGraph}}
		\inputminted[tabsize=2,breaklines,firstline=19,lastline=38,fontsize=\small]{c++}{flow.cpp}
		
		\subsection{Algoritmo de Edmonds-Karp $O(VE^2)$}
		\inputminted[tabsize=2,breaklines,firstline=82,lastline=108,fontsize=\small]{c++}{flow.cpp}
		
		\subsection{Algoritmo de Dinic $O(V^2E)$}
		\inputminted[tabsize=2,breaklines,firstline=40,lastline=80,fontsize=\small]{c++}{flow.cpp}
		
		\subsection{Flujo máximo de costo mínimo}
		\inputminted[tabsize=2,breaklines,firstline=110,lastline=145,fontsize=\small]{c++}{flow.cpp}
		
		\subsection{Hungariano}
		\inputminted[tabsize=2,breaklines,firstline=148,lastline=202,fontsize=\small]{c++}{flow.cpp}
		
	\newpage
	\section{Estructuras de datos}
		\subsection{Segment Tree}
			\subsubsection{Minimalistic: Point updates, range queries}
			\inputminted[tabsize=2,breaklines,firstline=4,lastline=47,fontsize=\small]{c++}{queries.cpp}
			
			\subsubsection{Dynamic: Range updates and range queries}
			\inputminted[tabsize=2,breaklines,firstline=49,lastline=100,fontsize=\small]{c++}{queries.cpp}
			
			\subsubsection{Static: Range updates and range queries}
			\inputminted[tabsize=2,breaklines,firstline=102,lastline=171,fontsize=\small]{c++}{queries.cpp}
			
			\subsubsection{Persistent: Point updates, range queries}
			\inputminted[tabsize=2,breaklines,firstline=173,lastline=203,fontsize=\small]{c++}{queries.cpp}
		
		\subsection{Fenwick Tree}
		\inputminted[tabsize=2,breaklines,firstline=205,lastline=242,fontsize=\small]{c++}{queries.cpp}
		
		\subsection{SQRT Decomposition}
		\inputminted[tabsize=2,breaklines,firstline=244,lastline=322,fontsize=\small]{c++}{queries.cpp}
		
		\subsection{AVL Tree}
		\inputminted[tabsize=2,breaklines,firstline=324,lastline=529,fontsize=\small]{c++}{queries.cpp}
		
		\subsection{Treap}
		\inputminted[tabsize=2,breaklines,firstline=531,lastline=796,fontsize=\small]{c++}{queries.cpp}
		
		\subsection{Sparse table}
			\subsubsection{Normal}
			\inputminted[tabsize=2,breaklines,firstline=798,lastline=833,fontsize=\small]{c++}{queries.cpp}
		
			\subsubsection{Disjoint}
			\inputminted[tabsize=2,breaklines,firstline=835,lastline=868,fontsize=\small]{c++}{queries.cpp}
			
		\subsection{Wavelet Tree}
		\inputminted[tabsize=2,breaklines,firstline=870,lastline=933,fontsize=\small]{c++}{queries.cpp}
		
		\subsection{Ordered Set C++}
		\inputminted[tabsize=2,breaklines,firstline=935,lastline=969,fontsize=\small]{c++}{queries.cpp}
		
		\subsection{HLD}
		\inputminted[tabsize=2,breaklines,firstline=971,lastline=1037,fontsize=\small]{c++}{queries.cpp}
		
		\subsection{Splay Tree}
		
		
		\subsection{Red Black Tree}
		
		
	\newpage
	\section{Cadenas}
		\subsection{Trie}
		\inputminted[tabsize=2,breaklines,firstline=144,lastline=196,fontsize=\small]{c++}{strings.cpp}
		
		\subsection{KMP}
		\inputminted[tabsize=2,breaklines,firstline=4,lastline=39,fontsize=\small]{c++}{strings.cpp}
		
		\subsection{Aho-Corasick}
		\inputminted[tabsize=2,breaklines,firstline=41,lastline=142,fontsize=\small]{c++}{strings.cpp}

		\subsection{Suffix Automaton}
		\inputminted[tabsize=2,breaklines,firstline=198,lastline=239,fontsize=\small]{c++}{strings.cpp}
		
		\subsection{Función Z}
		\inputminted[tabsize=2,breaklines,firstline=241,lastline=253,fontsize=\small]{c++}{strings.cpp}
		
		\subsection{Manacher}
		\inputminted[tabsize=2,breaklines,firstline=255,lastline=283,fontsize=\small]{c++}{strings.cpp}
	
	\newpage
	\section{Varios}
		\subsection{Lectura y escritura de \texttt{\_\_int128}}
		\inputminted[tabsize=2,breaklines,firstline=46,lastline=83,fontsize=\small]{c++}{misc.cpp}
		
		\subsection{Longest Common Subsequence (LCS)}
		\inputminted[tabsize=2,breaklines,firstline=21,lastline=33,fontsize=\small]{c++}{misc.cpp}
		
		\subsection{Longest Increasing Subsequence (LIS)}
		\inputminted[tabsize=2,breaklines,firstline=5,lastline=19,fontsize=\small]{c++}{misc.cpp}
		
		\subsection{Levenshtein Distance}
		\inputminted[tabsize=2,breaklines,firstline=145,lastline=156,fontsize=\small]{c++}{misc.cpp}
		
		\subsection{Día de la semana}
		\inputminted[tabsize=2,breaklines,firstline=35,lastline=44,fontsize=\small]{c++}{misc.cpp}
		
		\subsection{2SAT}
		\inputminted[tabsize=2,breaklines,firstline=85,lastline=128,fontsize=\small]{c++}{misc.cpp}
		
		\subsection{Código Gray}
		\inputminted[tabsize=2,breaklines,firstline=130,lastline=143,fontsize=\small]{c++}{misc.cpp}
		
		\subsection{Contar número de unos en binario en un rango}
		\inputminted[tabsize=2,breaklines,firstline=158,lastline=165,fontsize=\small]{c++}{misc.cpp}
		
		\subsection{Números aleatorios en C++11}
		\inputminted[tabsize=2,breaklines,firstline=167,lastline=180,fontsize=\small]{c++}{misc.cpp}
		
		\subsection{Lower and upper bound}
		\inputminted[tabsize=2,breaklines,firstline=182,lastline=186,fontsize=\small]{c++}{misc.cpp}
		
	\newpage
	\section{Fórmulas y notas}
		\subsection{Números de Stirling del primer tipo}
			$\stirlingI{n}{k}$ representa el número de permutaciones de $n$ elementos en exactamente $k$ ciclos disjuntos.
			\begin{align*}
				\stirlingI{0}{0} &= 1 \\
				\stirlingI{0}{n} &= \stirlingI{n}{0} = 0 \quad &, \quad n>0 \\
				\stirlingI{n}{k} &= (n-1)\stirlingI{n-1}{k} + \stirlingI{n-1}{k-1} \quad &, \quad k>0 \\
				\sum_{k=0}^{n} \stirlingI{n}{k} &= n! \\
				\sum_{k=0}^{\infty} \stirlingI{n}{k} x^k &= \prod_{k=0}^{n-1}(x+k)
			\end{align*}
		
		\subsection{Números de Stirling del segundo tipo}
			$\stirlingII{n}{k}$ representa el número de formas de particionar un conjunto de $n$ objetos distinguibles en $k$ subconjuntos no vacíos.
			\begin{align*}
				\stirlingII{0}{0} &= 1 \\
				\stirlingII{0}{n} &= \stirlingII{n}{0} = 0 \quad &, \quad n>0 \\
				\stirlingII{n}{k} &= k\stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} \quad &, \quad k>0 \\
				&= \sum_{j=0}^{k} \dfrac{j^n}{j!} \cdot \dfrac{(-1)^{k-j}}{(k-j)!}
			\end{align*}
		
		\subsection{Números de Euler}
			$\euler{n}{k}$ representa el número de permutaciones de $1$ a $n$ en donde exactamente $k$ números son mayores que el número anterior, es decir, cuántas permutaciones tienen $k$ ``ascensos''.
			\begin{align*}
				\euler{1}{0} &= 1 \\
				\euler{n}{k} &= (n-k)\euler{n-1}{k-1} + (k+1)\euler{n-1}{k} \quad &, \quad n \geq 2 \\
				&= \sum_{j=0}^{k} (-1)^j \binom{n+1}{j} (k+1-j)^n \\
				\sum_{k=0}^{n-1} \euler{n}{k} &= n!
			\end{align*}
		
		\subsection{Números de Catalan}
			\begin{align*}
				C_0 &= 1 \\
				C_n &= \dfrac{1}{n+1}\binom{2n}{n} = \sum_{j=0}^{n-1} C_j C_{n-1-j} \\
				\sum_{n=0}^{\infty} C_n x^n &= \dfrac{1-\sqrt{1-4x}}{2x}
			\end{align*}
		
		\subsection{Números de Bell}
			$B_n$ representa el número de formas de particionar un conjunto de $n$ elementos.
			\begin{align*}
				B_n &= \sum_{k=0}^{n}\stirlingII{n}{k} = \sum_{k=0}^{n-1}\binom{n-1}{k} B_k \\
				\sum_{n=0}^{\infty} \dfrac{B_n}{n!}x^n &= e^{e^x-1}
			\end{align*}
		
		\subsection{Números de Bernoulli}
			\begin{align*}
				{B_0}^+ &= 1 \\
				{B_n}^+ &= 1 - \sum_{k=0}^{n-1}\binom{n}{k}\dfrac{{B_k}^+}{n-k+1} \\
				\sum_{n=0}^{\infty} \dfrac{{B_n}^+ x^n}{n!} &= \dfrac{x}{1-e^{-x}} = \dfrac{1}{\frac{1}{1!}-\frac{x}{2!}+\frac{x^2}{3!}-\frac{x^3}{4!}+\cdots}
			\end{align*}
		
		\subsection{Fórmula de Faulhaber}
			\begin{align*}
				S_p(n) &= \sum_{k=1}^{n}k^p = \dfrac{1}{p+1}\sum_{k=0}^{p} \binom{p+1}{k} {B_k}^+ n^{p+1-k}
			\end{align*}
		
		\subsection{Función Beta}
			\begin{align*}
				B(x,y) &= \dfrac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)} = 2 \int_{0}^{\pi/2} \sin^{2x-1}(\theta) \cos^{2x-1}(\theta) d\theta \\
				&= \int_{0}^{1} t^{x-1} (1-t)^{y-1} dt = \int_{0}^{\infty} \dfrac{t^{x-1}}{(1+t)^{x+y}} dt
			\end{align*}
			
		\subsection{Función zeta de Riemann}
			La siguiente fórmula converge rápido para valores pequeños de $n$ ($n \approx 20$):
			\begin{align*}
				\zeta(s) &\approx \dfrac{1}{d_0 (1 - 2^{1-s})} \sum_{k=1}^{n} \dfrac{(-1)^{k-1} d_k}{k^s} \\
				d_k &= \sum_{j=k}^{n} \dfrac{4^j}{n+j} \binom{n+j}{2j}
			\end{align*}
		
		\subsection{Funciones generadoras}
			\begin{align*}
				\sum_{n=0}^{\infty} \left( \sum_{k=0}^{n}a_k \right) x^n &= \dfrac{1}{1-x}\sum_{n=0}^{\infty} a_n x^n \\
				\sum_{n=0}^{\infty} \binom{n+k-1}{k-1}x^n &= \dfrac{1}{\left(1-x\right)^k} \\
				\sum_{n=0}^{\infty} p_n x^n &= \dfrac{1}{\displaystyle \prod_{k=1}^{\infty}(1-x^k)} = \dfrac{1}{\displaystyle \sum_{n=-\infty}^{\infty} (-1)^n x^{\frac{1}{2}n(3n+1)}} \\
				\sum_{p=0}^{\infty} \dfrac{S_p(n)}{p!} x^p &= \dfrac{e^{x(n+1)}-e^x}{e^x-1} \\
				\sum_{n=0}^{\infty} n^k x^n &= \dfrac{\displaystyle \sum_{i=0}^{k-1} \euler{k}{i} x^{i+1}}{(1-x)^{k+1}} \quad , \quad k \geq 1
			\end{align*}
			Sean $a_1, a_2, \ldots, a_n$ números complejos. Sean $p_m = \displaystyle \sum_{i=1}^{n} a_i^m$ y $s_m$ el $m$-ésimo polinomio elemental simétrico de $a_1, a_2, \ldots, a_n$. Entonces se cumple que $xS'(x) + P(x)S(x) = 0$, donde $P(x)=\displaystyle \sum_{m=1}^{\infty} p_m x^m$ y $S(x)=\displaystyle \prod_{i=1}^{n}(1-a_ix) = \sum_{m=0}^{n}(-1)^m s_m x^m$.
		
		\subsection{Números armónicos}
			\begin{align*}
				H_n &= \sum_{k=1}^{n} \dfrac{1}{k} \approx \ln(n) + \gamma + \dfrac{1}{2n} - \dfrac{1}{12n^2} \\
				\gamma &\approx 0.577215664901532860606512
			\end{align*}
		
		\subsection{Aproximación de Stirling}
			\begin{align*}
				\ln(n!) &\approx n\ln(n) - n + \dfrac{1}{2}\ln(2 \pi n) \\
				\text{\# de dígitos de $n!$} &= 1 + \left\lfloor n\log\left(\dfrac{n}{e}\right) + \dfrac{1}{2}\log(2 \pi n) \right\rfloor \quad \text{($n \geq 30$)}
			\end{align*}
		
		\subsection{Ternas pitagóricas}
			\begin{itemize}
				\item Una terna de enteros positivos $(a,b,c)$ es pitagórica si $a^2+b^2=c^2$. Además es primitiva si $\gcd(a,b,c)=1$.
				\item Generador de ternas primitivas:
				\begin{align*}
					a &= m^2-n^2 \\
					b &= 2mn \\
					c &= m^2+n^2
				\end{align*}
				donde $n \geq 1$, $m>n$, $\gcd(m,n)=1$ y $m,n$ tienen distinta paridad.
				\item Árbol de ternas pitagóricas primitivas: al multiplicar cualquiera de estas matrices:
				\begin{align*}
					\begin{pmatrix}
						1 & -2 & 2 \\
						2 & -1 & 2 \\
						2 & -2 & 3
					\end{pmatrix} \quad , \quad
					\begin{pmatrix}
						-1 & 2 & 2 \\
						-2 & 1 & 2 \\
						-2 & 2 & 3
					\end{pmatrix} \quad , \quad
					\begin{pmatrix}
						1 & 2 & 2 \\
						2 & 1 & 2 \\
						2 & 2 & 3
					\end{pmatrix}
				\end{align*}
				por una terna primitiva $\mathbf{v^T}$, obtenemos otra terna primitiva diferente. En particular, si empezamos con $\mathbf{v}=(3,4,5)$, podremos generar todas las ternas primitivas.
			\end{itemize}
	
		\subsection{Árbol de Stern–Brocot}
			Todos los racionales positivos se pueden representar como un árbol binario de búsqueda completo infinito con raíz $\frac{1}{1}$.
			\begin{itemize}
				\item Dado un racional $q=[a_0;a_1,a_2,\ldots,a_k]$ donde $a_k \neq 1$, sus hijos serán $[a_0;a_1,a_2,\ldots,a_k+1]$ y $[a_0;a_1,a_2,\ldots,a_k-1,2]$, y su padre será $[a_0;a_1,a_2,\ldots,a_k-1]$.
				\item Para hallar el camino de la raíz $\frac{1}{1}$ a un racional $q$, se usa búsqueda binaria iniciando con $L=\frac{0}{1}$ y $R=\frac{1}{0}$. Para hallar $M$ se supone que $L=\frac{a}{b}$ y $R=\frac{c}{d}$, entonces $M=\frac{a+c}{b+d}$.
			\end{itemize}
	
		\subsection{Combinatoria}
			\begin{itemize}
				\item Principio de las casillas: al colocar $n$ objetos en $k$ lugares hay al menos $\lceil \frac{n}{k} \rceil$ objetos en un mismo lugar.
				\item Número de funciones: sean $A$ y $B$ conjuntos con $m=\abs{A}$ y $n=\abs{B}$. Sea $f : A \to B$:
				\begin{itemize}
					\item Si $m \leq n$, entonces hay $\displaystyle m!\binom{n}{m}$ funciones inyectivas $f$.
					\item Si $m=n$, entonces hay $n!$ funciones biyectivas $f$.
					\item Si $m \geq n$, entonces hay $n!\stirlingII{m}{n}$ funciones suprayectivas $f$.
				\end{itemize}
				\item Barras y estrellas: ¿cuántas soluciones en los enteros no negativos tiene la ecuación $\displaystyle \sum_{i=1}^{k}x_i = n$? Tiene  $\displaystyle \binom{n+k-1}{k-1}$ soluciones.
				\item ¿Cuántas soluciones en los enteros positivos tiene la ecuación $\displaystyle \sum_{i=1}^{k}x_i = n$? Tiene  $\displaystyle \binom{n-1}{k-1}$ soluciones.
				\item Desordenamientos: $a_0=1$, $a_1=0$, $a_n=(n-1)(a_{n-1}+a_{n-2})=na_{n-1}+(-1)^n$.
				\item Sea $f(x)$ una función. Sea $g_n(x)=x g_{n-1}'(x)$ con $g_0(x)=f(x)$. Entonces $g_n(x)=\sum_{k=0}^{n} \stirlingII{n}{k} x^k f^{(k)}(x)$.
				\item Supongamos que tenemos $m+1$ puntos: $(0, y_0)$, $(1, y_1)$, $\ldots$, $(m, y_m)$. Entonces el polinomio $P(x)$ de grado $m$ que pasa por todos ellos es:
				\begin{align*}
					P(x) &= \left[ \prod_{i=0}^{m}(x-i) \right] (-1)^m \sum_{i=0}^{m} \dfrac{y_i (-1)^i}{(x-i)i!(m-i)!}
				\end{align*}
				\item Sea $a_0, a_1, \ldots$ una recurrencia lineal homogénea de grado $d$ dada por $\displaystyle a_n=\sum_{i=1}^{d} b_i a_{n-i}$ para $n \geq d$ con términos iniciales $a_0, a_1, \ldots, a_{d-1}$. Sean $A(x)$ y $B(x)$ las funciones generadoras de las sucesiones $a_n$ y $b_n$ respectivamente, entonces se cumple que $A(x)=\dfrac{A_0(x)}{1-B(x)}$, donde $\displaystyle A_0(x)=\sum_{i=0}^{d-1} \left[ a_i - \sum_{j=0}^{i-1}a_j b_{i-j} \right] x^i$.
				\item Si queremos obtener otra recurrencia $c_n$ tal que $c_n=a_{kn}$, las raíces del polinomio característico de $c_n$ se obtienen al elevar todas las raíces del polinomio característico de $a_n$ a la $k$-ésima potencia; y sus términos iniciales serán $a_0, a_k, \ldots, a_{k(d-1)}$.
			\end{itemize}
	
		\subsection{Grafos}
			\begin{itemize}
				\item Sea $d_n$ el número de grafos con $n$ vértices etiquetados: $\displaystyle d_n = 2^{\binom{n}{2}}$.
				\item Sea $c_n$ el número de grafos conexos con $n$ vértices etiquetados. Tenemos la recurrencia: $c_1=1$ y $\displaystyle d_n = \sum_{k=1}^{n} \binom{n-1}{k-1} c_k d_{n-k}$. También se cumple, usando funciones generadoras exponenciales, que $C(x)=1+\ln(D(x))$.
				\item Sea $t_n$ el número de torneos fuertemente conexos en $n$ nodos etiquetados. Tenemos la recurrencia $t_1=1$ y $\displaystyle d_n = \sum_{k=1}^{n} \binom{n}{k} t_k d_{n-k}$. Usando funciones generadoras exponenciales, tenemos que $T(x)=1-\dfrac{1}{D(x)}$.
				\item Número de spanning trees en un grafo completo con $n$ vértices etiquetados: $n^{n-2}$.
				\item Número de bosques etiquetados con $n$ vértices y $k$ componentes conexas: $kn^{n-k-1}$.
				\item Para un grafo no dirigido simple $G$ con $n$ vértices etiquetados de $1$ a $n$, sea $Q=D-A$, donde $D$ es la matriz diagonal de los grados de cada nodo de $G$ y $A$ es la matriz de adyacencia de $G$. Entonces el número de spanning trees de $G$ es igual a cualquier cofactor de $Q$.
				\item Sea $G$ un grafo. Se define al polinomio $P_G(x)$ como el polinomio cromático de $G$, en donde $P_G(k)$ nos dice cuántas $k$-coloraciones de los vértices admite $G$. Ejemplos comunes:
				\begin{itemize}
					\item Grafo completo de $n$ nodos: $P(x)=x(x-1)(x-2) \ldots (x-(n-1))$
					\item Grafo vacío de $n$ nodos: $P(x)=x^n$
					\item Árbol de $n$ nodos: $P(x)=x(x-1)^{n-1}$
					\item Ciclo de $n$ nodos: $P(x)=(x-1)^n + (-1)^n(x-1)$
				\end{itemize}
			\end{itemize}
		
		\subsection{Teoría de números}
			\begin{align*}
				(f * e)(n) &= f(n) \\
				(\varphi * \mathbf{1})(n) &= n \\
				(\mu * \mathbf{1})(n) &= e(n) \\
				\varphi(n^k) &= n^{k-1}\varphi(n) \\
				\sum_{\substack{k=1	\\ \gcd(k,n)=1}}^{n} k &= \dfrac{n \varphi(n)}{2} \quad , \quad n \geq 2 \\
				\sum_{k=1}^{n} \text{lcm}(k,n) &= \dfrac{n}{2} + \dfrac{n}{2}\sum_{d | n} d\varphi(d) = \dfrac{n}{2} + \dfrac{n}{2} \prod_{p^a | n} \dfrac{p^{2a+1}+1}{p+1} \\
				\sum_{k=1}^{n} \gcd(k,n) &= \sum_{d | n} d\varphi\left(\dfrac{n}{d}\right) = \prod_{p^a | n} p^{a-1}(1+(a+1)(p-1))
			\end{align*}
		
			\begin{itemize}
				\item Lifting the exponent: sea $p$ un primo, $x,y$ enteros y $n$ un entero positivo tal que $p \mid x-y$ pero $p \nmid x$ ni $p \nmid y$. Entonces:
				\begin{itemize}
					\item Si $p$ es impar: $v_p(x^n-y^n) = v_p(x-y) + v_p(n)$
					\item Si $p=2$ y $n$ es par: $v_p(x^n-y^n) = v_p(x-y) + v_p(n) + v_p(x+y) - 1$
				\end{itemize}
				donde $v_p(n)$ es el exponente de $p$ en la factorización en primos de $n$.
				\item Suma de dos cuadrados: sea $\chi_4(n)$ una función multiplicativa igual a 1 si $n \equiv 1 \mod 4$, $-1$ si $n \equiv 3 \mod 4$ y cero en otro caso. Entonces, el número de soluciones enteras $(a,b)$ de la ecuación $a^2+b^2=n$ es $4(\chi_4 * 1)(n) = 4 \displaystyle \sum_{d | n} \chi_4(d)$.
				\item Teorema de Lucas:
				\begin{align*}
					\binom{m}{n} &\equiv \prod_{i=0}^{k} \binom{m_i}{k_i} \pmod{p} \\
					m = \sum_{i=0}^{k} m_i p^i \quad &, \quad n = \sum_{i=0}^{k} n_i p^i \\
					0 \leq m_i &, n_i < p
				\end{align*}
				
				\item Sean $a,b,c \in \mathbb{Z}$ con $a \neq 0$ y $b \neq 0$. La ecuación $ax+by=c$ tiene como soluciones:
				\begin{align*}
					x &= \dfrac{x_0 c - bk}{d} \\
					y &= \dfrac{y_0 c + ak}{d} 
				\end{align*}
				para toda $k \in \mathbb{Z}$ si y solo si $d | c$, donde $ax_0+by_0=\gcd(a,b)=d$ (Euclides extendido). Si $a$ y $b$ tienen el mismo signo, hay exactamente $\max\left( \left\lfloor\dfrac{x_0 c}{\abs{b}}\right\rfloor + \left\lfloor\dfrac{y_0 c}{\abs{a}}\right\rfloor + 1, 0 \right)$ soluciones no negativas. Si tienen el signo distinto, hay infinitas soluciones no negativas.
				
				\item Dada una función aritmética $f$ con $f(1) \neq 0$, existe otra función aritmética $g$ tal que $(f*g)(n)=e(n)$, dada por:
				\begin{align*}
					g(1) &= \dfrac{1}{f(1)} \\
					g(n) &= -\dfrac{1}{f(1)} \sum_{d | n, d<n} f\left(\dfrac{n}{d}\right)g(d) \quad , \quad n > 1
				\end{align*}
				
				\item Sean $\displaystyle h(n) = \sum_{k=1}^{n} f\left(\left\lfloor \dfrac{n}{k} \right\rfloor\right) g(k)$, $\displaystyle G(n)=\sum_{k=1}^{n}g(k)$ y $m=\left\lfloor \sqrt{n} \right\rfloor$, entonces:
				\begin{align*}
					h(n) &= \sum_{k=1}^{\lfloor n/m \rfloor}f\left(\left\lfloor \dfrac{n}{k} \right\rfloor\right) g(k) + \sum_{k=1}^{m-1} \left( G\left(\left\lfloor \dfrac{n}{k} \right\rfloor\right) - G\left(\left\lfloor \dfrac{n}{k+1} \right\rfloor\right) \right)f(k)
				\end{align*}
				
				\item Sean $\displaystyle F(n)=\sum_{k=1}^{n}f(k)$, $\displaystyle G(n)=\sum_{k=1}^{n}g(k)$, $\displaystyle h(n)=(f * g)(n)=\sum_{d | n}f(d)g\left(\dfrac{n}{d}\right)$ y $\displaystyle H(n)=\sum_{k=1}^{n}h(k)$, entonces:
				\begin{align*}
					H(n) &= \sum_{k=1}^{n}f(k)G\left(\left\lfloor \dfrac{n}{k} \right\rfloor\right)
				\end{align*}
				
				\item Sean $\displaystyle \Phi_p(n) = \sum_{k=1}^{n}k^p\varphi(k)$ y $\displaystyle M_p(n) = \sum_{k=1}^{n}k^p\mu(k)$. Aplicando lo anterior, podemos calcular $\Phi_p(n)$ y $M_p(n)$ con complejidad $O(n^{2/3})$ si precalculamos con fuerza bruta los primeros $\lfloor n^{2/3} \rfloor$ valores, y para los demás, usamos las siguientes recurrencias (DP con \texttt{map}):
				{\small
				\begin{align*}
					\Phi_p(n) &= S_{p+1}(n) - \sum_{k=2}^{\lfloor n/m \rfloor} k^p \Phi_p\left(\left\lfloor \dfrac{n}{k}  \right\rfloor\right) - \sum_{k=1}^{m-1} \left( S_p\left(\left\lfloor \dfrac{n}{k} \right\rfloor\right) - S_p\left(\left\lfloor \dfrac{n}{k+1} \right\rfloor\right) \right)\Phi_p(k) \\
					M_p(n) &= 1 - \sum_{k=2}^{\lfloor n/m \rfloor} k^p M_p\left(\left\lfloor \dfrac{n}{k}  \right\rfloor\right) - \sum_{k=1}^{m-1} \left( S_p\left(\left\lfloor \dfrac{n}{k} \right\rfloor\right) - S_p\left(\left\lfloor \dfrac{n}{k+1} \right\rfloor\right) \right)M_p(k)
				\end{align*}
				}
				
				\item En general, si queremos hallar $F(n)$ y existe una función mágica $g(n)$ tal que $G(n)$ y $H(n)$ se puedan calcular en $O(1)$, entonces:
				{\small
				\begin{align*}
					F(n) &= \dfrac{1}{g(1)} \left[ H(n) - \sum_{k=2}^{\lfloor n/m \rfloor} g(k)F\left(\left\lfloor \dfrac{n}{k} \right\rfloor\right) - \sum_{k=1}^{m-1} \left( G\left(\left\lfloor \dfrac{n}{k} \right\rfloor\right) - G\left(\left\lfloor \dfrac{n}{k+1} \right\rfloor\right) \right)F(k) \right]
				\end{align*}
				}
			\end{itemize}
			
		\subsection{Primos}
			$10^2+1$, $10^3+9$, $10^4+7$, $10^5+3$, $10^6+3$, $10^7+19$, $10^8+7$, $10^9+7$, $10^{10}+19$, $10^{11}+3$, $10^{12}+39$, $10^{13}+37$, $10^{14}+31$, $10^{15}+37$, $10^{16}+61$, $10^{17}+3$, $10^{18}+3$.
			
			$10^2-3$, $10^3-3$, $10^4-27$, $10^5-9$, $10^6-17$, $10^7-9$, $10^8-11$, $10^9-63$, $10^{10}-33$, $10^{11}-23$, $10^{12}-11$, $10^{13}-29$, $10^{14}-27$, $10^{15}-11$, $10^{16}-63$, $10^{17}-3$, $10^{18}-11$.
		
		\subsection{Números primos de Mersenne}
			Números primos de la forma $M_p=2^p-1$ con $p$ primo. Todos los números perfectos pares son de la forma $2^{p-1}M_p$ y viceversa.
		
			Los primeros 47 valores de $p$ son: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609.
		
		\subsection{Números primos de Fermat}
			Números primos de la forma $F_p=2^{2^p}+1$, solo se conocen cinco: 3, 5, 17, 257, 65537. Un polígono de $n$ lados es construible si y solo si $n$ es el producto de algunas potencias de dos y distintos primos de Fermat.

\end{document}