content/math/chineseRemainder.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct CRT {
	using lll = __int128;
	lll M = 1, sol = 0; // Solution unique modulo M
	bool hasSol = true;

	// Adds congruence x = a (mod m)
	void add(ll a, ll m) {
		auto [d, s, t] = extendedEuclid(M, m);
		if((a - sol) % d != 0) hasSol = false;
		lll z = M/d * s;
		M *= m/d;
		sol = (z % M * (a-sol) % M + sol + M) % M;
	}
};
% Colors, used for syntax highlighting.
% To print this document, set all colors to black!
\usepackage{xcolor}
\definecolor{safeRed}{HTML}{D7191C}
\definecolor{safeOrange}{HTML}{FFDE71}
\definecolor{safeYellow}{HTML}{FFFFBF}
\definecolor{safeGreen}{HTML}{99CF8F}
\definecolor{safeBlue}{HTML}{2B83BA}

%try printer friendly colors?
%\colorlet{keyword}{safeBlue}
%\colorlet{string}{safeRed}
%\colorlet{comment}{safeGreen}
%\colorlet{identifier}{black}
\definecolor{type}{HTML}{2750A0}
\definecolor{string}{HTML}{7B3294}
\definecolor{comment}{HTML}{1A9641}
\definecolor{identifier}{HTML}{000000}
\definecolor{keyword}{HTML}{900000}

% Source code listings.
\usepackage[scaled=0.80]{beramono}

\usepackage{listings}
\lstset{
	language={[11]C++},
	numbers=left,
	stepnumber=1,
	numbersep=6pt,
	numberstyle=\small,
	breaklines=true,
	breakautoindent=true,
	breakatwhitespace=false,
	numberblanklines=true,
	postbreak=\space,
	tabsize=2,
	upquote=true,
	basicstyle=\ttfamily\normalsize,
	showspaces=false,
	showstringspaces=false,
	extendedchars=true,
	keywordstyle=\color{keyword}\bfseries,
	stringstyle=\color{string}\bfseries,
	commentstyle=\color{comment}\bfseries\itshape,
	identifierstyle=\color{identifier},
	directivestyle=\color{keyword}\bfseries,
	emph={auto, int, long, long long, float, double, long double, char, bool, void, ll, ld, pt, lll, __int128, __float128, true, false, this, nullptr, INF, inf, EPS, eps},
	emphstyle=\color{type}\bfseries,
	frame=trbl,
	aboveskip=3pt,
	belowskip=3pt,
	deletestring=[b]{'},%fix digit separator but break char highlighting (fixed again with literate)
	escapechar=@
	%moredelim=**[is][{\btHL[fill=green!30,draw=red,dashed,thin]}]{@}{@}	
}

\newcommand{\formatChar}[1]{{\color{string}\bfseries\textquotesingle{}#1\textquotesingle{}}}

% Listings doesn't support UTF8. This is just enough for German umlauts. and commonly used chars
\lstset{literate=%
  {'a'}{{\formatChar{a}}}3
  {'z'}{{\formatChar{z}}}3
  {'A'}{{\formatChar{A}}}3
  {'Z'}{{\formatChar{Z}}}3
  {'0'}{{\formatChar{0}}}3
  {'1'}{{\formatChar{1}}}3
  {'\$'}{{\formatChar{\$}}}3
  {'\#'}{{\formatChar{\#}}}3
  {Ö}{{\"O}}1
  {Ä}{{\"A}}1
  {Ü}{{\"U}}1
  {ß}{{\ss}}1
  {ü}{{\"u}}1
  {ä}{{\"a}}1
  {ö}{{\"o}}1
  {~}{{\textasciitilde}}1
}

\makeatletter
\let\orig@lstnumber=\thelstnumber
\newcommand\lstresetnumber{\global\let\thelstnumber=\orig@lstnumber}
\let\orig@placelstnumber=\lst@PlaceNumber
\gdef\lst@PlaceNumber{\orig@placelstnumber\lstresetnumber}
\newcommand\lstsettmpnumber[1]{\gdef\thelstnumber{#1}}

\lst@AddToHook{OnEmptyLine}{%
	\ifnum\value{lstnumber}>99
		\lstsettmpnumber{\_\_\_}
	\else\ifnum\value{lstnumber}>9
		\lstsettmpnumber{\_\_}
	\else
		\lstsettmpnumber{\_}
	\fi\fi
%	\lstsettmpnumber{\_\_\kern-6pt}%
	\vspace{-1.75ex}%
	\addtocounter{lstnumber}{-1}%
}
% old: (change numberblanklines=false!)
%\lst@AddToHook{OnEmptyLine}{%
%	\vspace{\dimexpr\baselineskip+0.5em}%
%	\addtocounter{lstnumber}{-1}%
%}

\newenvironment{btHighlight}[1][]
{\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}}
{\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup}

\newcommand\btHL[1][]{%
	\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv%
	}
	\def\bt@HL@endenv{%
	\end{btHighlight}%
	\egroup%
}
\newcommand{\bt@HL@box}[2][]{%
	\tikz[#1]{%
		\pgfpathrectangle{\pgfpoint{1pt}{0pt}}{\pgfpoint{\wd #2}{\ht #2}}%
		\pgfusepath{use as bounding box}%
		\node[anchor=base west, fill=orange!30,outer sep=0pt,inner xsep=2.2pt, inner ysep=0pt, rounded corners=3pt, minimum height=\ht\strutbox+1pt,#1]{\raisebox{1pt}{\strut}\strut\usebox{#2}};
	}%
}

\newcommand{\hl}[1]{\btHL[fill=safeOrange,draw=black,thin]{#1}}

\ifthenelse{\isundefined{\gitorigin}}{}{	
	\usepackage{ocgx2}
	\usepackage{fontawesome}
	\lst@AddToHook{Init}{%
		\ifthenelse{\equal{\lst@name}{}}{}{%
			\begin{minipage}[t][0pt]{\linewidth}%
				\vspace{0pt}%
				\hfill%
				\begin{ocg}[printocg=never]{Source links}{srclinks}{1}%
					\hfill\href{\gitorigin\lst@name}{\faExternalLink}%
				\end{ocg}%
			\end{minipage}%
		}%
	}
}
\makeatother