\documentclass[usenames]{beamer}
\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{amsmath}
\usepackage{array}
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}

\begin{document}
\begin{frame}[t]{Rozšírený Euklidov algoritmus (spätný)}

$(412,335)=\alt<1-14>{?}{}\alt<15->{1}{}$

	\begin{tabular}{rclcrcr|R{1cm}|R{2cm}|L{2cm}}
	\only<2>{$412$ & = & \textcolor{red}{$1$} & $\cdot$ & $335$ & + & \textcolor{blue}{$77$}\\}%
	\uncover<3->{%
		$412$ & = & \textcolor{red}{$1$} & $\cdot$ & \underline{$335$} & + & \textcolor{blue}{\underline{$77$}}%
		\only<32>{ & $\textcolor{cyan}{-87}$}%
		\only<33>{ & $\textcolor{cyan}{-87}$ & $\textcolor{cyan}{20} - \textcolor{red}{1}\cdot \textcolor{cyan}{(-87)}$}%
		\only<34->{ & $\textcolor{cyan}{-87}$ & $\textcolor{cyan}{107}$}%
	\\}%
	\only<4>{$335$ & = & \textcolor{red}{$4$} & $\cdot$ & $77$ & +& \textcolor{blue}{27}\\}%
	\uncover<5->{%
		$335$ & = & \textcolor{red}{$4$} & $\cdot$ & $\underline{77}$ & +& \textcolor{blue}{\underline{27}}%
		\only<29>{ & $\textcolor{cyan}{20}$}%
		\only<30>{ & $\textcolor{cyan}{20}$ & $\textcolor{cyan}{-7} - \textcolor{red}{4}\cdot \textcolor{cyan}{20}$}%
		\only<31->{ & $\textcolor{cyan}{20}$ & $\textcolor{cyan}{-87}$}%
	\\}%
	\only<6>{$77$ & = & \textcolor{red}{$2$} & $\cdot$ & $27$ & +& \textcolor{blue}{$23$}\\}%
	\uncover<7->{%
		$77$ & = & \textcolor{red}{$2$} & $\cdot$ & $\underline{27}$ & +& \textcolor{blue}{\underline{$23$}}%
		\only<26>{ & $\textcolor{cyan}{-7}$}%
		\only<27>{ & $\textcolor{cyan}{-7}$ & $\textcolor{cyan}{6} - \textcolor{red}{2}\cdot \textcolor{cyan}{(-7)}$}%
		\only<28->{ & $\textcolor{cyan}{-7}$ & $\textcolor{cyan}{20}$}%
	\\}%
	\only<8>{$27$ & = & \textcolor{red}{$1$} & $\cdot$ & $23$ & + & \textcolor{blue}{$4$}\\}%
	\uncover<9->{%
		$27$ & = & \textcolor{red}{$1$} & $\cdot$ & $\underline{23}$ & + & \textcolor{blue}{$\underline{4}$}%
		\only<23>{ & $\textcolor{cyan}{6}$}%
		\only<24>{ & $\textcolor{cyan}{6}$ & $\textcolor{cyan}{-1} - \textcolor{red}{1}\cdot \textcolor{cyan}{6}$}%
		\only<25->{ & $\textcolor{cyan}{6}$ & $\textcolor{cyan}{-7}$}%
	\\}%
	\only<10>{$23$ & = & \textcolor{red}{$5$} & $\cdot$ & $4$ & + & \textcolor{blue}{$3$}\\}%
	\uncover<11->{%
		$23$ & = & \textcolor{red}{$5$} & $\cdot$ & $\underline{4}$ & + & \textcolor{blue}{$\underline{3}$}%
		\only<20>{& $\textcolor{cyan}{-1}$}%
		\only<21>{& $\textcolor{cyan}{-1}$ & $\textcolor{cyan}{1} - \textcolor{red}{5}\cdot \textcolor{cyan}{(-1)}$}%
		\only<22->{& $\textcolor{cyan}{-1}$ & $\textcolor{cyan}{6}$}%
	\\}%
	\only<12>{$4$ & = & \textcolor{red}{$1$} & $\cdot$ & $3$ & + & \textcolor{blue}{$1$}\\}%
	\uncover<13->{%
		$4$ & = & \textcolor{red}{$1$} & $\cdot$ & \underline{$3$} & + & \textcolor{blue}{\underline{$1$}}%
		\only<15>{ & \multicolumn{3}{l|}{\textcolor{red}{$\leftarrow$}}}%
		\only<17>{ & $\textcolor{cyan}{1}$}%
		\only<18>{ & $\textcolor{cyan}{1}$ & $\textcolor{cyan}{0} - \textcolor{cyan}{1}\cdot \textcolor{red}{1}$}%
		\only<19->{ & $\textcolor{cyan}{1}$ & $\textcolor{cyan}{-1}$}%
	\\}%
	\only<14>{$3$ & = & \textcolor{red}{$3$} & $\cdot$ & $1$ & + & \textcolor{blue}{$0$}\\}%
	\uncover<15->{%
		$3$ & = & \textcolor{red}{$3$} & $\cdot$ & $1$ & + & \textcolor{gray}{$0$}%
		\only<15>{ & \multicolumn{3}{l|}{Máme nsd}}%
		\only<16->{& $\textcolor{cyan}{0}$ & $\textcolor{cyan}{1}$}%
	\\}%
		\only<15>{&&&&&&& \multicolumn{3}{c|}{posledný nenulový zvyšok}\\}%
\end{tabular}

\only<16->{\par\bigskip\textbf{Skúška správnosti:} %
	\only<16-18>{$\textcolor{cyan}{0}\cdot 3 + \textcolor{cyan}{1}\cdot 1 = \mbox{nsd}$}%
	\only<19-21>{$\textcolor{cyan}{1}\cdot 4 + \textcolor{cyan}{(-1)}\cdot 3 = \mbox{nsd}$}%
	\only<22-24>{$\textcolor{cyan}{(-1)} \cdot 23 + \textcolor{cyan}{6}\cdot 4 = \mbox{nsd}$}%
	\only<25-27>{$\textcolor{cyan}{6}\cdot 27 + \textcolor{cyan}{(-7)}\cdot 23 = \mbox{nsd}$}%
	\only<28-30>{$\textcolor{cyan}{(-7)}\cdot 77 + \textcolor{cyan}{20}\cdot 27 = \mbox{nsd}$}%
	\only<31-33>{$\textcolor{cyan}{20}\cdot 335 + \textcolor{cyan}{(-87)}\cdot 77 = \mbox{nsd}$}%
	\only<34->{$\textcolor{cyan}{(-87)}\cdot 412 + \textcolor{cyan}{107}\cdot 335 = \mbox{nsd}$}%
}%

\only<35>{\medskip\textbf{Výsledok:} $412\cdot \textcolor{cyan}{(-87)} + 335\cdot \textcolor{cyan}{107} = \textcolor{gray}{1} = (412,335)$}
\end{frame}

\begin{frame}[t]{Rozšírený Euklidov algoritmus (priamy)}
$(335,412)=?$

	\textbf{Interpretácia:} 
	
	\begin{center}
		$a_{orig} = 335$, $b_{orig} = 412$, 
		\begin{align*}
			a &= c\cdot b + r,\\ 
			a &= e \cdot a_{orig} + f\cdot b_{orig},\\
			b &= g \cdot a_{orig} + h\cdot b_{orig}.\\
		\end{align*}
	\end{center}

	\textbf{Aktualizácia:} 
	
	\begin{center}
		$a' = b$, $b' = r$

		$c' = a' / b'$ (celočíselné delenie)

		$r' = a' \mod b'$ (zvyšok)

		$e' = g$, $f' = h$

		$g' = e - c \cdot g$ ($c$ predošlé)

		$h' = f - c \cdot h$ ($c$ predošlé)



	\end{center}
\end{frame}


\begin{frame}[t]{Rozšírený Euklidov algoritmus (priamy)}
%	\newbox\t
%	\setbox\t=\hbox{$-13$}
%	\showthe\wd\t
	\begin{tabular}{cccC{0.8cm}R{0.69cm}R{0.69cm}R{2.0cm}R{1.8cm}}%
		\textbf{a} & \textbf{b} & \textbf{c} & \textbf{r} & \textbf{e} & \textbf{f} & \textbf{g} & \textbf{h} \\%
		\only<1->{%
			$335$ & $412$%
			\only<2->{ & \color<6>{red}{$0$} & $335$}%
			\only<3->{ & \color<6>{blue}{$1$} & \color<6>{green}{$0$} & \color<6>{blue}{$0$} & \color<6>{green}{$1$}}%
		}%
		\only<4->{\\%
			$412$ & $335$ & \color<10>{red}{$1$} & $77$%
			\only<5->{ & \color<10>{blue}{$0$} & \color<10>{green}{$1$}}%
			\only<6>{ & $\textcolor{blue}{1} - \textcolor{red}{0}\cdot \textcolor{blue}{0}$ & $\textcolor{green}{0} - \textcolor{red}{0}\cdot \textcolor{green}{1}$}%
			\only<7->{ & \color<10>{blue}{$1$} & \color<10>{green}{$0$}}%
		}%
		\only<8->{\\%
			$335$ & $77$ & \color<14>{red}{$4$} & $27$%
			\only<9->{& \color<14>{blue}{$1$} & \color<14>{green}{$0$}}%
			\only<10>{& $\textcolor{blue}{0} - \textcolor{red}{1}\cdot \textcolor{blue}{1}$ & $\textcolor{green}{1} - \textcolor{red}{1}\cdot \textcolor{green}{0}$}%
			\only<11->{& \color<14>{blue}{$-1$} & \color<14>{green}{$1$}}%
		}%
		\only<12->{\\%
			$77$ & $27$ & \color<18>{red}{$2$} & $23$%
			\only<13->{& \color<18>{blue}{$-1$} & \color<18>{green}{$1$}}%
			\only<14>{& $\textcolor{blue}{1} - \textcolor{red}{4}\cdot (\textcolor{blue}{-1})$ & $\textcolor{green}{0} - \textcolor{red}{4}\cdot \textcolor{green}{1}$}%
			\only<15->{& \color<18>{blue}{$5$} & \color<18>{green}{$-4$}}%
		}%
		\only<16->{\\%
			$27$ & $23$ & \color<22>{red}{$1$} & $4$
			\only<17->{& \color<22>{blue}{$5$} & \color<22>{green}{$-4$}}%
			\only<18>{& $\textcolor{blue}{-1} - \textcolor{red}{2}\cdot \textcolor{blue}{5}$ & $\textcolor{green}{1} - \textcolor{red}{2}\cdot (\textcolor{green}{-4})$}%
			\only<19->{& \color<22>{blue}{$-11$} & \color<22>{green}{$9$}}%
		}%
		\only<20->{\\%
			$23$ & $4$ & \color<26>{red}{$5$} & $3$%
			\only<21->{& \color<26>{blue}{$-11$} & \color<26>{green}{$9$}}%
			\only<22>{& $\textcolor{blue}{5} - \textcolor{red}{1}\cdot (\textcolor{blue}{-11})$ & $\textcolor{green}{-4} - \textcolor{red}{1}\cdot \textcolor{green}{9}$}%
			\only<23->{& \color<26>{blue}{$16$} & \color<26>{green}{$-13$}}%
		}%
		\only<24->{\\%
			$4$ & $3$ & \color<30>{red}{$1$} & $1$%
			\only<25->{& \color<30>{blue}{$16$} & \color<30>{green}{$-13$}}%
			\only<26>{& $\textcolor{blue}{-11} - \textcolor{red}{5}\cdot \textcolor{blue}{16}$ & $\textcolor{green}{9} - \textcolor{red}{5}\cdot (\textcolor{green}{-13})$}%
			\only<27->{& \color<30>{blue}{$-91$} & \color<30>{green}{$74$}}%
		}%
		\only<28->{\\%
			$3$ & \color<31>{red}{$1$} & $3$ & $0$%
			\only<29->{& $-91$ & $74$}%
			\only<30>{& $\textcolor{blue}{16} - \textcolor{red}{1}\cdot (\textcolor{blue}{-91})$ & $\textcolor{green}{-13} - \textcolor{red}{1}\cdot \textcolor{green}{74}$}%
			\only<31->{& \color<31>{blue}{$107$} & \color<31>{green}{$-87$}}%
		}%
	\end{tabular}%
	\only<31->{%

		\medskip
		\textbf{Výsledok:} $335\cdot \textcolor{blue}{107} + 412\cdot (\textcolor{green}{-87}) = \textcolor{red}{1} = (335, 412)$%
	}%
\end{frame}
\end{document}
