sengi's journal

如何求解 $\dot{x} = x+f(t)$

Posted on 2021-09-29 Edited on 2021-07-01 In math

\[ \begin{equation} \def\pr{\text{\rm pr}} \def\sec{\text{\rm sect}} \def\R{\mathbb{R}} \def\N{\mathbb{N}} \def\C{\mathbb{C}} \def\Z{\mathbb{Z}} \def\H{\mathcal{H}} \def\beq{\begin{equation}} \def\endeq{\end{equation}} \def\lesim{\lesssim} \def\mc{\mathcal} \def\h{\mathcal{H}} \newcommand{\bram}[1]{\begin{bmatrix}#1\end{bmatrix}} \def\mn{M^{(n)}} \def\lam{\lambda} \def\wide{\widehat} \def\uk{u^{(k_0)}} \def\uo{u^{(0)}} \def\pj{P^{(2)}} \def\pii{P^{(1)}} \def\pc{P^{Cone}} \def\tx{\tilde x} \DeclareMathOperator{\re}{Re} \DeclareMathOperator{\sgn}{sgn} \def\cplus{c\ci+} \def\cmin{c\ci-} \def\cplusmin{c\ci\pm} \def\chiplus{\chi\ci+} \def\chimin{\chi\ci-} \def\chiplusmin{\chi\ci\pm} \def\psiplus{\psi\ci+} \def\psimin{\psi\ci-} \def\psiplusmin{\psi\ci\pm} \def\sigmaplus{\sigma\ci+} \def\sigmamin{\sigma\ci-} \def\sigmaplusmin{\sigma\ci\pm} \def\bbone{\mathbbm 1} \newcommand{\dil}{\text{\rm Dil}} \newcommand{\spec}{\operatorname{spec}} \newcommand{\ls}{\lesssim} \newcommand{\sL}{\mathscr L} \newcommand{\sJ}{\mathscr J} \newcommand{\sK}{\mathscr K} \newcommand{\wh}{\widehat} \newcommand{\wt}{\widetilde} \newcommand{\A}{\mathcal A} \newcommand{\E}{\mathcal E} \newcommand{\F}{\mathcal F} \newcommand{\D}{\mathcal D} \newcommand{\K}{\mathcal K} \newcommand{\QQ}{\mathcal Q} \newcommand{\RR}{\mathcal R} \newcommand{\f}[2]{\frac{#1}{#2}} \newcommand{\term}{c(z,r)F^\Psi_r(\cdot-z)} \newcommand{\norm}[1]{ \left| #1 \right| } \newcommand{\abs}[1]{ \left| #1 \right| } \newcommand{\Norm}[1]{ \left\| #1 \right\| } \newcommand{\iff}{\Leftrightarrow} \newcommand{\set}[1]{ \left\{ #1 \right\} } \newcommand{\Be}{\begin{equation}} \newcommand{\Ee}{\end{equation}} \newcommand{\Bm}{\begin{multline}} \newcommand{\Em}{\end{multline}} \newcommand{\Bea}{\begin{eqnarray}} \newcommand{\Eea}{\end{eqnarray}} \newcommand{\Beas}{\begin{eqnarray*}} \newcommand{\Eeas}{\end{eqnarray*}} \newcommand{\Benu}{\begin{enumerate}} \newcommand{\Eenu}{\end{enumerate}} \newcommand{\Bi}{\begin{itemize}} \newcommand{\Ei}{\end{itemize}} \def\conv{\text{Conv}} \def\tp{\tilde p} \def\tq{\tilde q} \def\crit{\text{\rm cr}} \def\sparse{\text{\rm sp}} \def\dyad{\text{\rm dyad}} \def\mart{\text{dyad}} \def\intslash{\rlap{\kern .32em $\mspace {.5mu}\backslash$ }\int} \def\qsl{\rlap{\kern .32em $\mspace {.5mu}\backslash$ }\int_{Q_x}} \def\Re{\operatorname{Re\,}} \def\Im{\operatorname{Im\,}} \def\mx \def\mn \def\vth{\vartheta} \def\rn{\rr^{n}} \def\rr{\mathbb R} \def\Q{\mathbb Q} \def\N{\mathbb N} \def\complex{\mathbb C} \def\emph#1{\it #1 } \def\diam{\text{\rm diam}} \def\osc{\text{\rm osc}} \def\ffB{\mathcal B} \def\seq{\subseteq} \def\Ga{\Gamma} \def\ga{\gamma} \def\Th{\Theta} \def\prd{\text{\it prod}} \def\parab{\text{\it parabolic}} \def\eg{\it e.g. } \def\cf{\it cf} \def\Rn{\mathbb R^n} \def\Rd{\mathbb R^d} \def\sgn{\text{\rm sign }} \def\rank{\text{\rm rank }} \def\corank{\text{\rm corank }} \def\coker{\text{\rm Coker }} \def\loc{\text{\rm loc}} \def\spec{\text{\rm spec}} \def\comp{\text{comp}} \def\Coi{C^\infty_0} \def\dist{\text{\it dist}} \def\diag{\text{\rm diag}} \def\supp{text{\rm supp}} \def\rad{\text{\it rad}} \def\sph{\text{sph}} \def\Lip{\text{\rm Lip}} \def\ev{\text{\rm ev}} \def\odd{\text{\rm odd}} \def\inn#1#2{\langle#1,#2\rangle} \def\biginn#1#2{\big\langle#1,#2\big\rangle} \def\rta{\rightarrow} \def\lta{\leftarrow} \def\noi{\noindent} \def\lcontr{\rfloor} \newcommand{\pmtx}[1]{\begin{pmatrix}#1\end{pmatrix}} \def\meas{\text{\rm meas}} \def\card{\text{\rm card}} \def\lc{\lesssim} \def\gc{\gtrsim} \def\pv{\text{\rm p.v.}} \def\a{\alpha} \def\alp{\alpha} \def\Alp{\Alpha} \def\bet{\beta} \def\gam{\gamma} \def\Gam{\Gamma} \def\del{\delta} \def\Del{\Delta} \def\eps{\varepsilon} \def\ep{\epsilon} \def\zet{\zeta} \def\tet{\theta} \def\Tet{\Theta} \def\iot{\iota} \def\kap{\kappa} \def\ka{\kappa} \def\lam{\lambda} \def\Lam{\Lambda} \def\la{\lambda} \def\La{\Lambda} \def\sig{\sigma} \def\Sig{\Sigma} \def\si{\sigma} \def\Si{\Sigma} \def\vphi{\varphi} \def\ome{\omega} \def\Ome{\Omega} \def\om{\omega} \def\fA{\mathfrak {A}} \def\fB{\mathfrak {B}} \def\fC{\mathfrak {C}} \def\fD{\mathfrak {D}} \def\fE{\mathfrak {E}} \def\fF{\mathfrak {F}} \def\fG{mathfrak {G}} \def\fH{\mathfrak {H}} \def\fI{\mathfrak {I}} \def\fJ{\mathfrak {J}} \def\fK{\mathfrak {K}} \def\fL{\mathfrak {L}} \def\fM{\mathfrak {M}} \def\fN{\mathfrak {N}} \def\fO{\mathfrak {O}} \def\fP{\mathfrak {P}} \def\fQ{\mathfrak {Q}} \def\fR{\mathfrak {R}} \def\fS{\mathfrak {S}} \def\fT{\mathfrak {T}} \def\fU{\mathfrak {U}} \def\fV{\mathfrak {V}} \def\fW{\mathfrak {W}} \def\fX{\mathfrak {X}} \def\fY{\mathfrak {Y}} \def\fZ{\mathfrak {Z}} \def\fa{\mathfrak {a}} \def\fb{\mathfrak {b}} \def\fc{\mathfrak {c}} \def\fd{\mathfrak {d}} \def\fe{\mathfrak {e}} \def\ff{\mathfrak {f}} \def\fg{\mathfrak {g}} \def\fh{\mathfrak {h}} \def\fj{\mathfrak {j}} \def\fk{\mathfrak {k}} \def\fl{\mathfrak {l}} \def\fn{\mathfrak {n}} \def\fo{\mathfrak {o}} \def\fq{\mathfrak {q}} \def\fr{\mathfrak {r}} \def\fs{\mathfrak {s}} \def\ft{\mathfrak {t}} \def\fu{\mathfrak {u}} \def\fv{\mathfrak {v}} \def\fw{\mathfrak {w}} \def\fx{\mathfrak {x}} \def\fy{\mathfrak {y}} \def\fz{\mathfrak {z}} \def\bbA{\mathbb {A}} \def\bbB{\mathbb {B}} \def\bbC{\mathbb {C}} \def\bbD{\mathbb {D}} \def\bbE{\mathbb {E}} \def\bbF{\mathbb {F}} \def\bbG{\mathbb {G}} \def\bbH{\mathbb {H}} \def\bbI{\mathbb {I}} \def\bbJ{\mathbb {J}} \def\bbK{\mathbb {K}} \def\bbL{\mathbb {L}} \def\bbM{\mathbb {M}} \def\bbN{\mathbb {N}} \def\bbO{\mathbb {O}} \def\bbP{\mathbb {P}} \def\bbQ{\mathbb {Q}} \def\bbR{\mathbb {R}} \def\bbS{\mathbb {S}} \def\bbT{\mathbb {T}} \def\bbU{\mathbb {U}} \def\bbV{\mathbb {V}} \def\bbW{\mathbb {W}} \def\bbX{\mathbb {X}} \def\bbY{\mathbb {Y}} \def\bbZ{\mathbb {Z}} \def\cA{\mathcal {A}} \def\cB{\mathcal {B}} \def\cC{\mathcal {C}} \def\cD{\mathcal {D}} \def\cE{\mathcal {E}} \def\cF{\mathcal {F}} \def\cG{\mathcal {G}} \def\cH{\mathcal {H}} \def\cI{\mathcal {I}} \def\cJ{\mathcal {J}} \def\cK{\mathcal {K}} \def\cL{\mathcal {L}} \def\cM{\mathcal {M}} \def\cN{\mathcal {N}} \def\cO{\mathcal {O}} \def\cP{\mathcal {P}} \def\cQ{\mathcal {Q}} \def\cR{\mathcal {R}} \def\cS{\mathcal {S}} \def\cT{\mathcal {T}} \def\cU{\mathcal {U}} \def\cV{\mathcal {V}} \def\cW{\mathcal {W}} \def\cX{\mathcal {X}} \def\cY{\mathcal {Y}} \def\cZ{\mathcal {Z}} \def\tA{\widetilde{A}} \def\tB{\widetilde{B}} \def\tC{\widetilde{C}} \def\tD{\widetilde{D}} \def\tE{\widetilde{E}} \def\tF{\widetilde{F}} \def\tG{\widetilde{G}} \def\tH{\widetilde{H}} \def\tI{\widetilde{I}} \def\tJ{\widetilde{J}} \def\tK{\widetilde{K}} \def\tL{\widetilde{L}} \def\tM{\widetilde{M}} \def\tN{\widetilde{N}} \def\tO{\widetilde{O}} \def\tP{\widetilde{P}} \def\tQ{\widetilde{Q}} \def\tR{\widetilde{R}} \def\tS{\widetilde{S}} \def\tT{\widetilde{T}} \def\tU{\widetilde{U}} \def\tV{\widetilde{V}} \def\tW{\widetilde{W}} \def\tX{\widetilde{X}} \def\tY{\widetilde{Y}} \def\tZ{\widetilde{Z}} \def\tcA{\widetilde{\mathcal {A}}} \def\tcB{\widetilde{\mathcal {B}}} \def\tcC{\widetilde{\mathcal {C}}} \def\tcD{\widetilde{\mathcal {D}}} \def\tcE{\widetilde{\mathcal {E}}} \def\tcF{\widetilde{\mathcal {F}}} \def\tcG{\widetilde{\mathcal {G}}} \def\tcH{\widetilde{\mathcal {H}}} \def\tcI{\widetilde{\mathcal {I}}} \def\tcJ{\widetilde{\mathcal {J}}} \def\tcK{\widetilde{\mathcal {K}}} \def\tcL{\widetilde{\mathcal {L}}} \def\tcM{\widetilde{\mathcal {M}}} \def\tcN{\widetilde{\mathcal {N}}} \def\tcO{\widetilde{\mathcal {O}}} \def\tcP{\widetilde{\mathcal {P}}} \def\tcQ{\widetilde{\mathcal {Q}}} \def\tcR{\widetilde{\mathcal {R}}} \def\tcS{\widetilde{\mathcal {S}}} \def\tcT{\widetilde{\mathcal {T}}} \def\tcU{\widetilde{\mathcal {U}}} \def\tcV{\widetilde{\mathcal {V}}} \def\tcW{\widetilde{\mathcal {W}}} \def\tcX{\widetilde{\mathcal {X}}} \def\tcY{\widetilde{\mathcal {Y}}} \def\tcZ{\widetilde{\mathcal {Z}}} \def\tfA{\widetilde{\mathfrak {A}}} \def\tfB{\widetilde{\mathfrak {B}}} \def\tfC{\widetilde{\mathfrak {C}}} \def\tfD{\widetilde{\mathfrak {D}}} \def\tfE{\widetilde{\mathfrak {E}}} \def\tfF{\widetilde{\mathfrak {F}}} \def\tfG{\widetilde{\mathfrak {G}}} \def\tfH{\widetilde{\mathfrak {H}}} \def\tfI{\widetilde{\mathfrak {I}}} \def\tfJ{\widetilde{\mathfrak {J}}} \def\tfK{\widetilde{\mathfrak {K}}} \def\tfL{\widetilde{\mathfrak {L}}} \def\tfM{\widetilde{\mathfrak {M}}} \def\tfN{\widetilde{\mathfrak {N}}} \def\tfO{\widetilde{\mathfrak {O}}} \def\tfP{\widetilde{\mathfrak {P}}} \def\tfQ{\widetilde{\mathfrak {Q}}} \def\tfR{\widetilde{\mathfrak {R}}} \def\tfS{\widetilde{\mathfrak {S}}} \def\tfT{\widetilde{\mathfrak {T}}} \def\tfU{\widetilde{\mathfrak {U}}} \def\tfV{\widetilde{\mathfrak {V}}} \def\tfW{\widetilde{\mathfrak {W}}} \def\tfX{\widetilde{\mathfrak {X}}} \def\tfY{\widetilde{\mathfrak {Y}}} \def\tfZ{\widetilde{\mathfrak {Z}}} \def\Atil{\widetilde A} \def\atil{\tilde a} \def\Btil{\widetilde B} \def\btil{\tilde b} \def\Ctil{\widetilde C} \def\ctil{\tilde c} \def\Dtil{\widetilde D} \def\dtil{\tilde d} \def\Etil{\widetilde E} \def\etil{\tilde e} \def\Ftil{\widetilde F} \def\ftil{\tilde f} \def\Gtil{\widetilde G} \def\gtil{\tilde g} \def\Htil{\widetilde H} \def\htil{\tilde h} \def\Itil{\widetilde I} \def\itil{\tilde i} \def\Jtil{\widetilde J} \def\jtil{\tilde j} \def\Ktil{\widetilde K} \def\ktil{\tilde k} \def\Ltil{\widetilde L} \def\ltil{\tilde l} \def\Mtil{\widetilde M} \def\mtil{\tilde m} \def\Ntil{\widetilde N} \def\ntil{\tilde n} \def\Otil{\widetilde O} \def\otil{\tilde o} \def\Ptil{\widetilde P} \def\ptil{\tilde p} \def\Qtil{\widetilde Q} \def\qtil{\tilde q} \def\Rtil{\widetilde R} \def\rtil{\tilde r} \def\Stil{\widetilde S} \def\stil{\tilde s} \def\Ttil{\widetilde T} \def\ttil{\tilde t} \def\Util{\widetilde U} \def\util{\tilde u} \def\Vtil{\widetilde V} \def\vtil{\tilde v} \def\Wtil{\widetilde W} \def\wtil{\tilde w} \def\Xtil{\widetilde X} \def\xtil{\tilde x} \def\Ytil{\widetilde Y} \def\ytil{\tilde y} \def\Ztil{\widetilde Z} \def\ztil{\tilde z} \def\ahat{\hat a} \def\Ahat{\widehat A} \def\bhat{\hat b} \def\Bhat{\widehat B} \def\chat{\hat c} \def\Chat{\widehat C} \def\dhat{\hat d} \def\Dhat{\widehat D} \def\ehat{\hat e} \def\Ehat{\widehat E} \def\fhat{\hat f} \def\Fhat{\widehat F} \def\ghat{\hat g} \def\Ghat{\widehat G} \def\hhat{\hat h} \def\Hhat{\widehat H} \def\ihat{\hat i} \def\Ihat{\widehat I} \def\jhat{\hat j} \def\Jhat{\widehat J} \def\khat{\hat k} \def\Khat{\widehat K} \def\lhat{\hat l} \def\Lhat{\widehat L} \def\mhat{\hat m} \def\Mhat{\widehat M} \def\nhat{\hat n} \def\Nhat{\widehat N} \def\ohat{\hat o} \def\Ohat{\widehat O} \def\phat{\hat p} \def\Phat{\widehat P} \def\qhat{\hat q} \def\Qhat{\widehat Q} \def\rhat{\hat r} \def\Rhat{\widehat R} \def\shat{\hat s} \def\Shat{\widehat S} \def\that{\hat t} \def\That{\widehat T} \def\uhat{\hat u} \def\Uhat{\widehat U} \def\vhat{\hat v} \def\Vhat{\widehat V} \def\what{\hat w} \def\What{\widehat W} \def\xhat{\hat x} \def\Xhat{\widehat X} \def\yhat{\hat y} \def\Yhat{\widehat Y} \def\zhat{\hat z} \def\Zhat{\widehat Z} \def\be#1{\begin{equation}\label{ #1}} \def\endeq{\end{equation}} \def\endal{\end{align}} \def\bas{\begin{align*}} \def\eas{\end{align*}} \def\bi{\begin{itemize}} \def\ei{\end{itemize}} \def\eps{\varepsilon} \def\textbf#1{\bf #1} \def\into{\hookrightarrow} \newcommand{\inf}{\infty} \newcommand{\os}[2]{\overset{#1}{#2}} \newcommand{\ms}{(X, \cM, \mu)} \newcommand{\salg}{\sig\text{-algebra}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\bij}{\mathrel{\hookrightarrow\hspace{-1.8ex}\to}} \newcommand{\onto}{\twoheadrightarrow} \newcommand{\id}{\text{id}} \newcommand{\Stab}{\text{Stab}} \def \bl {\backslash} \def \sfin {\sig\text{-finite}} \def \mum {\mu\text{-measurable}} \def \emps {\varnothing} \newcommand{\m}[1]{\boldsymbol{#1}} \newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\Inf}{\text{inf}} \newcommand{\wb}[1]{\overline{#1}} \newcommand{\lto}{\longrightarrow} \newcommand{\todo}[1]{\bf\color{red}{[ToDo] \text{#1}}} \newcommand{\char}[1]{\cX_{#1}} \newcommand{\fp}{f^+} \newcommand{\fm}{f^-} \newcommand{\infm}{\text{inf}} \newcommand{\onorm}[1]{\Norm{#1}_1} \newcommand{\tnorm}[1]{\Norm{#1}_2} \newcommand{\infn}[1]{\Norm{#1}_\inf} \newcommand{\pnorm}[1]{\Norm{#1}_p} \newcommand{\End}{\text{End}} \newcommand{\Ob}{\text{Ob}} \newcommand{\Hom}{\text{Hom}} \newcommand{\intall}{\int_{-\inf}^{\inf}} \newcommand{\intpmpi}{\int_{-\pi}^{\pi}} \newcommand{\div}{\bigr|} \newcommand{\when}{\biggr|} \def \bsp {\begin{split}} \def \esp {\end{split}} \def \bc {\begin{cases}} \def \ec {\end{cases}} \newcommand{\sech}{\text{sech}} \newcommand{\vectk}{\text{Vect}_\text{k}} \newcommand{\top}{\text{Top}} \newcommand{\grp}{\text{Grp}} \newcommand{\pathx}{\text{Paths}_X} \newcommand{\from}{\leftarrow} \newcommand{\lfrom}{\longleftarrow} \newcommand{\tofrom}[2]{\os{\xrightarrow{#1}}{\xleftarrow[#2]{}}} \newcommand{\sym}{\text{Sym}} \newcommand{\Set}{\text{Set}} \newcommand{\zn}{\Z/n\Z} \newcommand{\Mor}{\text{Mor}} \newcommand{\acton}{\circlearrowright} \DeclareMathOperator{\tr}{Tr} \newcommand{\par}{\partial} \newcommand{\Fun}{\text{Fun}} \newcommand{\triv}{\text{triv}} \newcommand{\zmnz}[1]{\Z/{#1}\Z} \newcommand{\tl}{\triangleleft} \newcommand{\paren}[1]{\left({#1}\right)} \newcommand{\ceil}[1]{\lceil{#1}\rceil} \newcommand{\floor}[1]{\lfloor{#1}\rfloor} \end{equation} \]

最近在看Dayan和Abbott的Theoretical Neuroscience。虽然是数学系学生但是由于太浪，分析代数几何都学了个遍，感觉哪科都没学好，于是后遗症就是像傅里叶变换这种极为重要的东西竟然不是很熟。于是我决定先把书后面的数学Appendix先光速过一遍，以免在读正文的时候尴尬卡壳。在附录讲微分方程的部分有一个方程： \[ \begin{equation} C\frac{dV}{dt} = \frac{E-V}{R} + I_e \end{equation} \] 这是比较容易求解的，令$W = -V+E+RI_e$, 我们有 \[ \begin{equation} RC(-W)' = W \end{equation} \] 愉快地分离变量就能得到$W = C'\exp(-t/\tau)$. 把$V(0)$ 这个初始条件代进去就有$C' = W(0) = -V(0)+E+RI_e$。我们就能得到书上列出的解 \[ \begin{equation} V(t) = V_\inf +(V(0)- V_\inf) \exp(-t/\tau) \end{equation} \]

Hello World

Posted on 2021-09-29 Edited on 2021-06-19

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

妙啊

Posted on 2021-09-29 Edited on 2020-12-25 In other

\[ \begin{equation} \def\pr{\text{\rm pr}} \def\sec{\text{\rm sect}} \def\R{\mathbb{R}} \def\N{\mathbb{N}} \def\C{\mathbb{C}} \def\Z{\mathbb{Z}} \def\H{\mathcal{H}} \def\beq{\begin{equation}} \def\endeq{\end{equation}} \def\lesim{\lesssim} \def\mc{\mathcal} \def\h{\mathcal{H}} \newcommand{\bram}[1]{\begin{bmatrix}#1\end{bmatrix}} \def\mn{M^{(n)}} \def\lam{\lambda} \def\wide{\widehat} \def\uk{u^{(k_0)}} \def\uo{u^{(0)}} \newcommand{\floor}[1]{\lfloor{#1}\rfloor} \def\pj{P^{(2)}} \def\pii{P^{(1)}} \def\pc{P^{Cone}} \def\tx{\tilde x} \DeclareMathOperator{\re}{Re} \DeclareMathOperator{\sgn}{sgn} \def\cplus{c\ci+} \def\cmin{c\ci-} \def\cplusmin{c\ci\pm} \def\chiplus{\chi\ci+} \def\chimin{\chi\ci-} \def\chiplusmin{\chi\ci\pm} \def\psiplus{\psi\ci+} \def\psimin{\psi\ci-} \def\psiplusmin{\psi\ci\pm} \def\sigmaplus{\sigma\ci+} \def\sigmamin{\sigma\ci-} \def\sigmaplusmin{\sigma\ci\pm} \def\bbone{\mathbbm 1} \newcommand{\dil}{\text{\rm Dil}} \newcommand{\spec}{\operatorname{spec}} \newcommand{\ls}{\lesssim} \newcommand{\sL}{\mathscr L} \newcommand{\sJ}{\mathscr J} \newcommand{\sK}{\mathscr K} \newcommand{\wh}{\widehat} \newcommand{\wt}{\widetilde} \newcommand{\A}{\mathcal A} \newcommand{\E}{\mathcal E} \newcommand{\F}{\mathcal F} \newcommand{\D}{\mathcal D} \newcommand{\K}{\mathcal K} \newcommand{\QQ}{\mathcal Q} \newcommand{\RR}{\mathcal R} \newcommand{\f}[2]{\frac{#1}{#2}} \newcommand{\term}{c(z,r)F^\Psi_r(\cdot-z)} \newcommand{\norm}[1]{ \left| #1 \right| } \newcommand{\abs}[1]{ \left| #1 \right| } \newcommand{\Norm}[1]{ \left\| #1 \right\| } \newcommand{\iff}{\Leftrightarrow} \newcommand{\set}[1]{ \left\{ #1 \right\} } \newcommand{\floor}[1]{\lfloor #1 \rfloor } \newcommand{\Be}{\begin{equation}} \newcommand{\Ee}{\end{equation}} \newcommand{\Bm}{\begin{multline}} \newcommand{\Em}{\end{multline}} \newcommand{\Bea}{\begin{eqnarray}} \newcommand{\Eea}{\end{eqnarray}} \newcommand{\Beas}{\begin{eqnarray*}} \newcommand{\Eeas}{\end{eqnarray*}} \newcommand{\Benu}{\begin{enumerate}} \newcommand{\Eenu}{\end{enumerate}} \newcommand{\Bi}{\begin{itemize}} \newcommand{\Ei}{\end{itemize}} \def\conv{\text{Conv}} \def\tp{\tilde p} \def\tq{\tilde q} \def\crit{\text{\rm cr}} \def\sparse{\text{\rm sp}} \def\dyad{\text{\rm dyad}} \def\mart{\text{dyad}} \def\intslash{\rlap{\kern .32em $\mspace {.5mu}\backslash$ }\int} \def\qsl{\rlap{\kern .32em $\mspace {.5mu}\backslash$ }\int_{Q_x}} \def\Re{\operatorname{Re\,}} \def\Im{\operatorname{Im\,}} \def\mx \def\mn \def\vth{\vartheta} \def\rn{\rr^{n}} \def\rr{\mathbb R} \def\Q{\mathbb Q} \def\N{\mathbb N} \def\complex{\mathbb C} \def\emph#1{\it #1 } \def\diam{\text{\rm diam}} \def\osc{\text{\rm osc}} \def\ffB{\mathcal B} \def\seq{\subseteq} \def\Ga{\Gamma} \def\ga{\gamma} \def\Th{\Theta} \def\prd{\text{\it prod}} \def\parab{\text{\it parabolic}} \def\eg{\it e.g. } \def\cf{\it cf} \def\Rn{\mathbb R^n} \def\Rd{\mathbb R^d} \def\sgn{\text{\rm sign }} \def\rank{\text{\rm rank }} \def\corank{\text{\rm corank }} \def\coker{\text{\rm Coker }} \def\loc{\text{\rm loc}} \def\spec{\text{\rm spec}} \def\comp{\text{comp}} \def\Coi{C^\infty_0} \def\dist{\text{\it dist}} \def\diag{\text{\rm diag}} \def\supp{text{\rm supp}} \def\rad{\text{\it rad}} \def\sph{\text{sph}} \def\Lip{\text{\rm Lip}} \def\ev{\text{\rm ev}} \def\odd{\text{\rm odd}} \def\inn#1#2{\langle#1,#2\rangle} \def\biginn#1#2{\big\langle#1,#2\big\rangle} \def\rta{\rightarrow} \def\lta{\leftarrow} \def\noi{\noindent} \def\lcontr{\rfloor} \newcommand{\pmtx}[1]{\begin{pmatrix}#1\end{pmatrix}} \def\meas{\text{\rm meas}} \def\card{\text{\rm card}} \def\lc{\lesssim} \def\gc{\gtrsim} \def\pv{\text{\rm p.v.}} \def\a{\alpha} \def\alp{\alpha} \def\Alp{\Alpha} \def\bet{\beta} \def\gam{\gamma} \def\Gam{\Gamma} \def\del{\delta} \def\Del{\Delta} \def\eps{\varepsilon} \def\ep{\epsilon} \def\zet{\zeta} \def\tet{\theta} \def\Tet{\Theta} \def\iot{\iota} \def\kap{\kappa} \def\ka{\kappa} \def\lam{\lambda} \def\Lam{\Lambda} \def\la{\lambda} \def\La{\Lambda} \def\sig{\sigma} \def\Sig{\Sigma} \def\si{\sigma} \def\Si{\Sigma} \def\vphi{\varphi} \def\ome{\omega} \def\Ome{\Omega} \def\om{\omega} \def\fA{\mathfrak {A}} \def\fB{\mathfrak {B}} \def\fC{\mathfrak {C}} \def\fD{\mathfrak {D}} \def\fE{\mathfrak {E}} \def\fF{\mathfrak {F}} \def\fG{mathfrak {G}} \def\fH{\mathfrak {H}} \def\fI{\mathfrak {I}} \def\fJ{\mathfrak {J}} \def\fK{\mathfrak {K}} \def\fL{\mathfrak {L}} \def\fM{\mathfrak {M}} \def\fN{\mathfrak {N}} \def\fO{\mathfrak {O}} \def\fP{\mathfrak {P}} \def\fQ{\mathfrak {Q}} \def\fR{\mathfrak {R}} \def\fS{\mathfrak {S}} \def\fT{\mathfrak {T}} \def\fU{\mathfrak {U}} \def\fV{\mathfrak {V}} \def\fW{\mathfrak {W}} \def\fX{\mathfrak {X}} \def\fY{\mathfrak {Y}} \def\fZ{\mathfrak {Z}} \def\fa{\mathfrak {a}} \def\fb{\mathfrak {b}} \def\fc{\mathfrak {c}} \def\fd{\mathfrak {d}} \def\fe{\mathfrak {e}} \def\ff{\mathfrak {f}} \def\fg{\mathfrak {g}} \def\fh{\mathfrak {h}} \def\fj{\mathfrak {j}} \def\fk{\mathfrak {k}} \def\fl{\mathfrak {l}} \def\fn{\mathfrak {n}} \def\fo{\mathfrak {o}} \def\fq{\mathfrak {q}} \def\fr{\mathfrak {r}} \def\fs{\mathfrak {s}} \def\ft{\mathfrak {t}} \def\fu{\mathfrak {u}} \def\fv{\mathfrak {v}} \def\fw{\mathfrak {w}} \def\fx{\mathfrak {x}} \def\fy{\mathfrak {y}} \def\fz{\mathfrak {z}} \def\bbA{\mathbb {A}} \def\bbB{\mathbb {B}} \def\bbC{\mathbb {C}} \def\bbD{\mathbb {D}} \def\bbE{\mathbb {E}} \def\bbF{\mathbb {F}} \def\bbG{\mathbb {G}} \def\bbH{\mathbb {H}} \def\bbI{\mathbb {I}} \def\bbJ{\mathbb {J}} \def\bbK{\mathbb {K}} \def\bbL{\mathbb {L}} \def\bbM{\mathbb {M}} \def\bbN{\mathbb {N}} \def\bbO{\mathbb {O}} \def\bbP{\mathbb {P}} \def\bbQ{\mathbb {Q}} \def\bbR{\mathbb {R}} \def\bbS{\mathbb {S}} \def\bbT{\mathbb {T}} \def\bbU{\mathbb {U}} \def\bbV{\mathbb {V}} \def\bbW{\mathbb {W}} \def\bbX{\mathbb {X}} \def\bbY{\mathbb {Y}} \def\bbZ{\mathbb {Z}} \def\cA{\mathcal {A}} \def\cB{\mathcal {B}} \def\cC{\mathcal {C}} \def\cD{\mathcal {D}} \def\cE{\mathcal {E}} \def\cF{\mathcal {F}} \def\cG{\mathcal {G}} \def\cH{\mathcal {H}} \def\cI{\mathcal {I}} \def\cJ{\mathcal {J}} \def\cK{\mathcal {K}} \def\cL{\mathcal {L}} \def\cM{\mathcal {M}} \def\cN{\mathcal {N}} \def\cO{\mathcal {O}} \def\cP{\mathcal {P}} \def\cQ{\mathcal {Q}} \def\cR{\mathcal {R}} \def\cS{\mathcal {S}} \def\cT{\mathcal {T}} \def\cU{\mathcal {U}} \def\cV{\mathcal {V}} \def\cW{\mathcal {W}} \def\cX{\mathcal {X}} \def\cY{\mathcal {Y}} \def\cZ{\mathcal {Z}} \def\tA{\widetilde{A}} \def\tB{\widetilde{B}} \def\tC{\widetilde{C}} \def\tD{\widetilde{D}} \def\tE{\widetilde{E}} \def\tF{\widetilde{F}} \def\tG{\widetilde{G}} \def\tH{\widetilde{H}} \def\tI{\widetilde{I}} \def\tJ{\widetilde{J}} \def\tK{\widetilde{K}} \def\tL{\widetilde{L}} \def\tM{\widetilde{M}} \def\tN{\widetilde{N}} \def\tO{\widetilde{O}} \def\tP{\widetilde{P}} \def\tQ{\widetilde{Q}} \def\tR{\widetilde{R}} \def\tS{\widetilde{S}} \def\tT{\widetilde{T}} \def\tU{\widetilde{U}} \def\tV{\widetilde{V}} \def\tW{\widetilde{W}} \def\tX{\widetilde{X}} \def\tY{\widetilde{Y}} \def\tZ{\widetilde{Z}} \def\tcA{\widetilde{\mathcal {A}}} \def\tcB{\widetilde{\mathcal {B}}} \def\tcC{\widetilde{\mathcal {C}}} \def\tcD{\widetilde{\mathcal {D}}} \def\tcE{\widetilde{\mathcal {E}}} \def\tcF{\widetilde{\mathcal {F}}} \def\tcG{\widetilde{\mathcal {G}}} \def\tcH{\widetilde{\mathcal {H}}} \def\tcI{\widetilde{\mathcal {I}}} \def\tcJ{\widetilde{\mathcal {J}}} \def\tcK{\widetilde{\mathcal {K}}} \def\tcL{\widetilde{\mathcal {L}}} \def\tcM{\widetilde{\mathcal {M}}} \def\tcN{\widetilde{\mathcal {N}}} \def\tcO{\widetilde{\mathcal {O}}} \def\tcP{\widetilde{\mathcal {P}}} \def\tcQ{\widetilde{\mathcal {Q}}} \def\tcR{\widetilde{\mathcal {R}}} \def\tcS{\widetilde{\mathcal {S}}} \def\tcT{\widetilde{\mathcal {T}}} \def\tcU{\widetilde{\mathcal {U}}} \def\tcV{\widetilde{\mathcal {V}}} \def\tcW{\widetilde{\mathcal {W}}} \def\tcX{\widetilde{\mathcal {X}}} \def\tcY{\widetilde{\mathcal {Y}}} \def\tcZ{\widetilde{\mathcal {Z}}} \def\tfA{\widetilde{\mathfrak {A}}} \def\tfB{\widetilde{\mathfrak {B}}} \def\tfC{\widetilde{\mathfrak {C}}} \def\tfD{\widetilde{\mathfrak {D}}} \def\tfE{\widetilde{\mathfrak {E}}} \def\tfF{\widetilde{\mathfrak {F}}} \def\tfG{\widetilde{\mathfrak {G}}} \def\tfH{\widetilde{\mathfrak {H}}} \def\tfI{\widetilde{\mathfrak {I}}} \def\tfJ{\widetilde{\mathfrak {J}}} \def\tfK{\widetilde{\mathfrak {K}}} \def\tfL{\widetilde{\mathfrak {L}}} \def\tfM{\widetilde{\mathfrak {M}}} \def\tfN{\widetilde{\mathfrak {N}}} \def\tfO{\widetilde{\mathfrak {O}}} \def\tfP{\widetilde{\mathfrak {P}}} \def\tfQ{\widetilde{\mathfrak {Q}}} \def\tfR{\widetilde{\mathfrak {R}}} \def\tfS{\widetilde{\mathfrak {S}}} \def\tfT{\widetilde{\mathfrak {T}}} \def\tfU{\widetilde{\mathfrak {U}}} \def\tfV{\widetilde{\mathfrak {V}}} \def\tfW{\widetilde{\mathfrak {W}}} \def\tfX{\widetilde{\mathfrak {X}}} \def\tfY{\widetilde{\mathfrak {Y}}} \def\tfZ{\widetilde{\mathfrak {Z}}} \def\Atil{\widetilde A} \def\atil{\tilde a} \def\Btil{\widetilde B} \def\btil{\tilde b} \def\Ctil{\widetilde C} \def\ctil{\tilde c} \def\Dtil{\widetilde D} \def\dtil{\tilde d} \def\Etil{\widetilde E} \def\etil{\tilde e} \def\Ftil{\widetilde F} \def\ftil{\tilde f} \def\Gtil{\widetilde G} \def\gtil{\tilde g} \def\Htil{\widetilde H} \def\htil{\tilde h} \def\Itil{\widetilde I} \def\itil{\tilde i} \def\Jtil{\widetilde J} \def\jtil{\tilde j} \def\Ktil{\widetilde K} \def\ktil{\tilde k} \def\Ltil{\widetilde L} \def\ltil{\tilde l} \def\Mtil{\widetilde M} \def\mtil{\tilde m} \def\Ntil{\widetilde N} \def\ntil{\tilde n} \def\Otil{\widetilde O} \def\otil{\tilde o} \def\Ptil{\widetilde P} \def\ptil{\tilde p} \def\Qtil{\widetilde Q} \def\qtil{\tilde q} \def\Rtil{\widetilde R} \def\rtil{\tilde r} \def\Stil{\widetilde S} \def\stil{\tilde s} \def\Ttil{\widetilde T} \def\ttil{\tilde t} \def\Util{\widetilde U} \def\util{\tilde u} \def\Vtil{\widetilde V} \def\vtil{\tilde v} \def\Wtil{\widetilde W} \def\wtil{\tilde w} \def\Xtil{\widetilde X} \def\xtil{\tilde x} \def\Ytil{\widetilde Y} \def\ytil{\tilde y} \def\Ztil{\widetilde Z} \def\ztil{\tilde z} \def\ahat{\hat a} \def\Ahat{\widehat A} \def\bhat{\hat b} \def\Bhat{\widehat B} \def\chat{\hat c} \def\Chat{\widehat C} \def\dhat{\hat d} \def\Dhat{\widehat D} \def\ehat{\hat e} \def\Ehat{\widehat E} \def\fhat{\hat f} \def\Fhat{\widehat F} \def\ghat{\hat g} \def\Ghat{\widehat G} \def\hhat{\hat h} \def\Hhat{\widehat H} \def\ihat{\hat i} \def\Ihat{\widehat I} \def\jhat{\hat j} \def\Jhat{\widehat J} \def\khat{\hat k} \def\Khat{\widehat K} \def\lhat{\hat l} \def\Lhat{\widehat L} \def\mhat{\hat m} \def\Mhat{\widehat M} \def\nhat{\hat n} \def\Nhat{\widehat N} \def\ohat{\hat o} \def\Ohat{\widehat O} \def\phat{\hat p} \def\Phat{\widehat P} \def\qhat{\hat q} \def\Qhat{\widehat Q} \def\rhat{\hat r} \def\Rhat{\widehat R} \def\shat{\hat s} \def\Shat{\widehat S} \def\that{\hat t} \def\That{\widehat T} \def\uhat{\hat u} \def\Uhat{\widehat U} \def\vhat{\hat v} \def\Vhat{\widehat V} \def\what{\hat w} \def\What{\widehat W} \def\xhat{\hat x} \def\Xhat{\widehat X} \def\yhat{\hat y} \def\Yhat{\widehat Y} \def\zhat{\hat z} \def\Zhat{\widehat Z} \def\be#1{\begin{equation}\label{ #1}} \def\endeq{\end{equation}} \def\endal{\end{align}} \def\bas{\begin{align*}} \def\eas{\end{align*}} \def\bi{\begin{itemize}} \def\ei{\end{itemize}} \def\eps{\varepsilon} \def\textbf#1{\bf #1} \def\into{\hookrightarrow} \def\inf{\infty} \newcommand{\os}[2]{\overset{#1}{#2}} \newcommand{\ms}{(X, \cM, \mu)} \newcommand{\salg}{\sig\text{-algebra}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\bij}{\mathrel{\hookrightarrow\hspace{-1.8ex}\to}} \newcommand{\onto}{\twoheadrightarrow} \newcommand{\id}{\text{id}} \newcommand{\Stab}{\text{Stab}} \def \bl {\backslash} \def \sfin {\sig\text{-finite}} \def \mum {\mu\text{-measurable}} \def \emps {\varnothing} \newcommand{\m}[1]{\boldsymbol{#1}} \newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\Inf}{\text{inf}} \newcommand{\wb}[1]{\overline{#1}} \newcommand{\lto}{\longrightarrow} \newcommand{\todo}[1]{\bf\color{red}{[ToDo] \text{#1}}} \newcommand{\char}[1]{\cX_{#1}} \newcommand{\fp}{f^+} \newcommand{\fm}{f^-} \newcommand{\infm}{\text{inf}} \newcommand{\onorm}[1]{\Norm{#1}_1} \newcommand{\tnorm}[1]{\Norm{#1}_2} \newcommand{\infn}[1]{\Norm{#1}_\inf} \newcommand{\pnorm}[1]{\Norm{#1}_p} \newcommand{\End}{\text{End}} \newcommand{\Ob}{\text{Ob}} \newcommand{\Hom}{\text{Hom}} \newcommand{\intall}{\int_{-\inf}^{\inf}} \newcommand{\intpmpi}{\int_{-\pi}^{\pi}} \newcommand{\div}{\bigr|} \newcommand{\when}{\biggr|} \def \bsp {\begin{split}} \def \esp {\end{split}} \def \bc {\begin{cases}} \def \ec {\end{cases}} \newcommand{\sech}{\text{sech}} \newcommand{\vectk}{\text{Vect}_\text{k}} \newcommand{\top}{\text{Top}} \newcommand{\grp}{\text{Grp}} \newcommand{\pathx}{\text{Paths}_X} \newcommand{\from}{\leftarrow} \newcommand{\lfrom}{\longleftarrow} \newcommand{\tofrom}[2]{\os{\xrightarrow{#1}}{\xleftarrow[#2]{}}} \newcommand{\sym}{\text{Sym}} \newcommand{\Set}{\text{Set}} \newcommand{\zn}{\Z/n\Z} \newcommand{\Mor}{\text{Mor}} \newcommand{\acton}{\circlearrowright} \DeclareMathOperator{\tr}{Tr} \newcommand{\par}{\partial} \newcommand{\Fun}{\text{Fun}} \newcommand{\triv}{\text{triv}} \newcommand{\zmnz}[1]{\Z/{#1}\Z} \newcommand{\tl}{\triangleleft} \newcommand{\paren}[1]{\left({#1}\right)} \newcommand{\ceil}[1]{\lceil{#1}\rceil} \newcommand{\floor}[1]{\lfloor{#1}\rfloor} \end{equation} \]

忙活了半天总算把latex的macro搞好了，接下来就可以轻松愉快地打公式了（误 \[ \begin{equation} e=\floor{m_1}c^2 \end{equation} \] 感谢下列文章/回答：

https://www.jianshu.com/p/a9f26f4cd4e6

https://github.com/hexojs/hexo/issues/2231

Sprague-Grundy Theorem and the Game of Nim

Posted on 2021-07-18

\[ \begin{equation} \def\pr{\text{\rm pr}} \def\sec{\text{\rm sect}} \def\R{\mathbb{R}} \def\N{\mathbb{N}} \def\C{\mathbb{C}} \def\Z{\mathbb{Z}} \def\H{\mathcal{H}} \def\beq{\begin{equation}} \def\endeq{\end{equation}} \def\lesim{\lesssim} \def\mc{\mathcal} \def\h{\mathcal{H}} \newcommand{\bram}[1]{\begin{bmatrix}#1\end{bmatrix}} \def\mn{M^{(n)}} \def\lam{\lambda} \def\wide{\widehat} \def\uk{u^{(k_0)}} \def\uo{u^{(0)}} \def\pj{P^{(2)}} \def\pii{P^{(1)}} \def\pc{P^{Cone}} \def\tx{\tilde x} \DeclareMathOperator{\re}{Re} \DeclareMathOperator{\sgn}{sgn} \def\cplus{c\ci+} \def\cmin{c\ci-} \def\cplusmin{c\ci\pm} \def\chiplus{\chi\ci+} \def\chimin{\chi\ci-} \def\chiplusmin{\chi\ci\pm} \def\psiplus{\psi\ci+} \def\psimin{\psi\ci-} \def\psiplusmin{\psi\ci\pm} \def\sigmaplus{\sigma\ci+} \def\sigmamin{\sigma\ci-} \def\sigmaplusmin{\sigma\ci\pm} \def\bbone{\mathbbm 1} \newcommand{\dil}{\text{\rm Dil}} \newcommand{\spec}{\operatorname{spec}} \newcommand{\ls}{\lesssim} \newcommand{\sL}{\mathscr L} \newcommand{\sJ}{\mathscr J} \newcommand{\sK}{\mathscr K} \newcommand{\wh}{\widehat} \newcommand{\wt}{\widetilde} \newcommand{\A}{\mathcal A} \newcommand{\E}{\mathcal E} \newcommand{\F}{\mathcal F} \newcommand{\D}{\mathcal D} \newcommand{\K}{\mathcal K} \newcommand{\QQ}{\mathcal Q} \newcommand{\RR}{\mathcal R} \newcommand{\f}[2]{\frac{#1}{#2}} \newcommand{\term}{c(z,r)F^\Psi_r(\cdot-z)} \newcommand{\norm}[1]{ \left| #1 \right| } \newcommand{\abs}[1]{ \left| #1 \right| } \newcommand{\Norm}[1]{ \left\| #1 \right\| } \newcommand{\iff}{\Leftrightarrow} \newcommand{\set}[1]{ \left\{ #1 \right\} } \newcommand{\Be}{\begin{equation}} \newcommand{\Ee}{\end{equation}} \newcommand{\Bm}{\begin{multline}} \newcommand{\Em}{\end{multline}} \newcommand{\Bea}{\begin{eqnarray}} \newcommand{\Eea}{\end{eqnarray}} \newcommand{\Beas}{\begin{eqnarray*}} \newcommand{\Eeas}{\end{eqnarray*}} \newcommand{\Benu}{\begin{enumerate}} \newcommand{\Eenu}{\end{enumerate}} \newcommand{\Bi}{\begin{itemize}} \newcommand{\Ei}{\end{itemize}} \def\conv{\text{Conv}} \def\tp{\tilde p} \def\tq{\tilde q} \def\crit{\text{\rm cr}} \def\sparse{\text{\rm sp}} \def\dyad{\text{\rm dyad}} \def\mart{\text{dyad}} \def\intslash{\rlap{\kern .32em $\mspace {.5mu}\backslash$ }\int} \def\qsl{\rlap{\kern .32em $\mspace {.5mu}\backslash$ }\int_{Q_x}} \def\Re{\operatorname{Re\,}} \def\Im{\operatorname{Im\,}} \def\mx \def\mn \def\vth{\vartheta} \def\rn{\rr^{n}} \def\rr{\mathbb R} \def\Q{\mathbb Q} \def\N{\mathbb N} \def\complex{\mathbb C} \def\emph#1{\it #1 } \def\diam{\text{\rm diam}} \def\osc{\text{\rm osc}} \def\ffB{\mathcal B} \def\seq{\subseteq} \def\Ga{\Gamma} \def\ga{\gamma} \def\Th{\Theta} \def\prd{\text{\it prod}} \def\parab{\text{\it parabolic}} \def\eg{\it e.g. } \def\cf{\it cf} \def\Rn{\mathbb R^n} \def\Rd{\mathbb R^d} \def\sgn{\text{\rm sign }} \def\rank{\text{\rm rank }} \def\corank{\text{\rm corank }} \def\coker{\text{\rm Coker }} \def\loc{\text{\rm loc}} \def\spec{\text{\rm spec}} \def\comp{\text{comp}} \def\Coi{C^\infty_0} \def\dist{\text{\it dist}} \def\diag{\text{\rm diag}} \def\supp{text{\rm supp}} \def\rad{\text{\it rad}} \def\sph{\text{sph}} \def\Lip{\text{\rm Lip}} \def\ev{\text{\rm ev}} \def\odd{\text{\rm odd}} \def\inn#1#2{\langle#1,#2\rangle} \def\biginn#1#2{\big\langle#1,#2\big\rangle} \def\rta{\rightarrow} \def\lta{\leftarrow} \def\noi{\noindent} \def\lcontr{\rfloor} \newcommand{\pmtx}[1]{\begin{pmatrix}#1\end{pmatrix}} \def\meas{\text{\rm meas}} \def\card{\text{\rm card}} \def\lc{\lesssim} \def\gc{\gtrsim} \def\pv{\text{\rm p.v.}} \def\a{\alpha} \def\alp{\alpha} \def\Alp{\Alpha} \def\bet{\beta} \def\gam{\gamma} \def\Gam{\Gamma} \def\del{\delta} \def\Del{\Delta} \def\eps{\varepsilon} \def\ep{\epsilon} \def\zet{\zeta} \def\tet{\theta} \def\Tet{\Theta} \def\iot{\iota} \def\kap{\kappa} \def\ka{\kappa} \def\lam{\lambda} \def\Lam{\Lambda} \def\la{\lambda} \def\La{\Lambda} \def\sig{\sigma} \def\Sig{\Sigma} \def\si{\sigma} \def\Si{\Sigma} \def\vphi{\varphi} \def\ome{\omega} \def\Ome{\Omega} \def\om{\omega} \def\fA{\mathfrak {A}} \def\fB{\mathfrak {B}} \def\fC{\mathfrak {C}} \def\fD{\mathfrak {D}} \def\fE{\mathfrak {E}} \def\fF{\mathfrak {F}} \def\fG{mathfrak {G}} \def\fH{\mathfrak {H}} \def\fI{\mathfrak {I}} \def\fJ{\mathfrak {J}} \def\fK{\mathfrak {K}} \def\fL{\mathfrak {L}} \def\fM{\mathfrak {M}} \def\fN{\mathfrak {N}} \def\fO{\mathfrak {O}} \def\fP{\mathfrak {P}} \def\fQ{\mathfrak {Q}} \def\fR{\mathfrak {R}} \def\fS{\mathfrak {S}} \def\fT{\mathfrak {T}} \def\fU{\mathfrak {U}} \def\fV{\mathfrak {V}} \def\fW{\mathfrak {W}} \def\fX{\mathfrak {X}} \def\fY{\mathfrak {Y}} \def\fZ{\mathfrak {Z}} \def\fa{\mathfrak {a}} \def\fb{\mathfrak {b}} \def\fc{\mathfrak {c}} \def\fd{\mathfrak {d}} \def\fe{\mathfrak {e}} \def\ff{\mathfrak {f}} \def\fg{\mathfrak {g}} \def\fh{\mathfrak {h}} \def\fj{\mathfrak {j}} \def\fk{\mathfrak {k}} \def\fl{\mathfrak {l}} \def\fn{\mathfrak {n}} \def\fo{\mathfrak {o}} \def\fq{\mathfrak {q}} \def\fr{\mathfrak {r}} \def\fs{\mathfrak {s}} \def\ft{\mathfrak {t}} \def\fu{\mathfrak {u}} \def\fv{\mathfrak {v}} \def\fw{\mathfrak {w}} \def\fx{\mathfrak {x}} \def\fy{\mathfrak {y}} \def\fz{\mathfrak {z}} \def\bbA{\mathbb {A}} \def\bbB{\mathbb {B}} \def\bbC{\mathbb {C}} \def\bbD{\mathbb {D}} \def\bbE{\mathbb {E}} \def\bbF{\mathbb {F}} \def\bbG{\mathbb {G}} \def\bbH{\mathbb {H}} \def\bbI{\mathbb {I}} \def\bbJ{\mathbb {J}} \def\bbK{\mathbb {K}} \def\bbL{\mathbb {L}} \def\bbM{\mathbb {M}} \def\bbN{\mathbb {N}} \def\bbO{\mathbb {O}} \def\bbP{\mathbb {P}} \def\bbQ{\mathbb {Q}} \def\bbR{\mathbb {R}} \def\bbS{\mathbb {S}} \def\bbT{\mathbb {T}} \def\bbU{\mathbb {U}} \def\bbV{\mathbb {V}} \def\bbW{\mathbb {W}} \def\bbX{\mathbb {X}} \def\bbY{\mathbb {Y}} \def\bbZ{\mathbb {Z}} \def\cA{\mathcal {A}} \def\cB{\mathcal {B}} \def\cC{\mathcal {C}} \def\cD{\mathcal {D}} \def\cE{\mathcal {E}} \def\cF{\mathcal {F}} \def\cG{\mathcal {G}} \def\cH{\mathcal {H}} \def\cI{\mathcal {I}} \def\cJ{\mathcal {J}} \def\cK{\mathcal {K}} \def\cL{\mathcal {L}} \def\cM{\mathcal {M}} \def\cN{\mathcal {N}} \def\cO{\mathcal {O}} \def\cP{\mathcal {P}} \def\cQ{\mathcal {Q}} \def\cR{\mathcal {R}} \def\cS{\mathcal {S}} \def\cT{\mathcal {T}} \def\cU{\mathcal {U}} \def\cV{\mathcal {V}} \def\cW{\mathcal {W}} \def\cX{\mathcal {X}} \def\cY{\mathcal {Y}} \def\cZ{\mathcal {Z}} \def\tA{\widetilde{A}} \def\tB{\widetilde{B}} \def\tC{\widetilde{C}} \def\tD{\widetilde{D}} \def\tE{\widetilde{E}} \def\tF{\widetilde{F}} \def\tG{\widetilde{G}} \def\tH{\widetilde{H}} \def\tI{\widetilde{I}} \def\tJ{\widetilde{J}} \def\tK{\widetilde{K}} \def\tL{\widetilde{L}} \def\tM{\widetilde{M}} \def\tN{\widetilde{N}} \def\tO{\widetilde{O}} \def\tP{\widetilde{P}} \def\tQ{\widetilde{Q}} \def\tR{\widetilde{R}} \def\tS{\widetilde{S}} \def\tT{\widetilde{T}} \def\tU{\widetilde{U}} \def\tV{\widetilde{V}} \def\tW{\widetilde{W}} \def\tX{\widetilde{X}} \def\tY{\widetilde{Y}} \def\tZ{\widetilde{Z}} \def\tcA{\widetilde{\mathcal {A}}} \def\tcB{\widetilde{\mathcal {B}}} \def\tcC{\widetilde{\mathcal {C}}} \def\tcD{\widetilde{\mathcal {D}}} \def\tcE{\widetilde{\mathcal {E}}} \def\tcF{\widetilde{\mathcal {F}}} \def\tcG{\widetilde{\mathcal {G}}} \def\tcH{\widetilde{\mathcal {H}}} \def\tcI{\widetilde{\mathcal {I}}} \def\tcJ{\widetilde{\mathcal {J}}} \def\tcK{\widetilde{\mathcal {K}}} \def\tcL{\widetilde{\mathcal {L}}} \def\tcM{\widetilde{\mathcal {M}}} \def\tcN{\widetilde{\mathcal {N}}} \def\tcO{\widetilde{\mathcal {O}}} \def\tcP{\widetilde{\mathcal {P}}} \def\tcQ{\widetilde{\mathcal {Q}}} \def\tcR{\widetilde{\mathcal {R}}} \def\tcS{\widetilde{\mathcal {S}}} \def\tcT{\widetilde{\mathcal {T}}} \def\tcU{\widetilde{\mathcal {U}}} \def\tcV{\widetilde{\mathcal {V}}} \def\tcW{\widetilde{\mathcal {W}}} \def\tcX{\widetilde{\mathcal {X}}} \def\tcY{\widetilde{\mathcal {Y}}} \def\tcZ{\widetilde{\mathcal {Z}}} \def\tfA{\widetilde{\mathfrak {A}}} \def\tfB{\widetilde{\mathfrak {B}}} \def\tfC{\widetilde{\mathfrak {C}}} \def\tfD{\widetilde{\mathfrak {D}}} \def\tfE{\widetilde{\mathfrak {E}}} \def\tfF{\widetilde{\mathfrak {F}}} \def\tfG{\widetilde{\mathfrak {G}}} \def\tfH{\widetilde{\mathfrak {H}}} \def\tfI{\widetilde{\mathfrak {I}}} \def\tfJ{\widetilde{\mathfrak {J}}} \def\tfK{\widetilde{\mathfrak {K}}} \def\tfL{\widetilde{\mathfrak {L}}} \def\tfM{\widetilde{\mathfrak {M}}} \def\tfN{\widetilde{\mathfrak {N}}} \def\tfO{\widetilde{\mathfrak {O}}} \def\tfP{\widetilde{\mathfrak {P}}} \def\tfQ{\widetilde{\mathfrak {Q}}} \def\tfR{\widetilde{\mathfrak {R}}} \def\tfS{\widetilde{\mathfrak {S}}} \def\tfT{\widetilde{\mathfrak {T}}} \def\tfU{\widetilde{\mathfrak {U}}} \def\tfV{\widetilde{\mathfrak {V}}} \def\tfW{\widetilde{\mathfrak {W}}} \def\tfX{\widetilde{\mathfrak {X}}} \def\tfY{\widetilde{\mathfrak {Y}}} \def\tfZ{\widetilde{\mathfrak {Z}}} \def\Atil{\widetilde A} \def\atil{\tilde a} \def\Btil{\widetilde B} \def\btil{\tilde b} \def\Ctil{\widetilde C} \def\ctil{\tilde c} \def\Dtil{\widetilde D} \def\dtil{\tilde d} \def\Etil{\widetilde E} \def\etil{\tilde e} \def\Ftil{\widetilde F} \def\ftil{\tilde f} \def\Gtil{\widetilde G} \def\gtil{\tilde g} \def\Htil{\widetilde H} \def\htil{\tilde h} \def\Itil{\widetilde I} \def\itil{\tilde i} \def\Jtil{\widetilde J} \def\jtil{\tilde j} \def\Ktil{\widetilde K} \def\ktil{\tilde k} \def\Ltil{\widetilde L} \def\ltil{\tilde l} \def\Mtil{\widetilde M} \def\mtil{\tilde m} \def\Ntil{\widetilde N} \def\ntil{\tilde n} \def\Otil{\widetilde O} \def\otil{\tilde o} \def\Ptil{\widetilde P} \def\ptil{\tilde p} \def\Qtil{\widetilde Q} \def\qtil{\tilde q} \def\Rtil{\widetilde R} \def\rtil{\tilde r} \def\Stil{\widetilde S} \def\stil{\tilde s} \def\Ttil{\widetilde T} \def\ttil{\tilde t} \def\Util{\widetilde U} \def\util{\tilde u} \def\Vtil{\widetilde V} \def\vtil{\tilde v} \def\Wtil{\widetilde W} \def\wtil{\tilde w} \def\Xtil{\widetilde X} \def\xtil{\tilde x} \def\Ytil{\widetilde Y} \def\ytil{\tilde y} \def\Ztil{\widetilde Z} \def\ztil{\tilde z} \def\ahat{\hat a} \def\Ahat{\widehat A} \def\bhat{\hat b} \def\Bhat{\widehat B} \def\chat{\hat c} \def\Chat{\widehat C} \def\dhat{\hat d} \def\Dhat{\widehat D} \def\ehat{\hat e} \def\Ehat{\widehat E} \def\fhat{\hat f} \def\Fhat{\widehat F} \def\ghat{\hat g} \def\Ghat{\widehat G} \def\hhat{\hat h} \def\Hhat{\widehat H} \def\ihat{\hat i} \def\Ihat{\widehat I} \def\jhat{\hat j} \def\Jhat{\widehat J} \def\khat{\hat k} \def\Khat{\widehat K} \def\lhat{\hat l} \def\Lhat{\widehat L} \def\mhat{\hat m} \def\Mhat{\widehat M} \def\nhat{\hat n} \def\Nhat{\widehat N} \def\ohat{\hat o} \def\Ohat{\widehat O} \def\phat{\hat p} \def\Phat{\widehat P} \def\qhat{\hat q} \def\Qhat{\widehat Q} \def\rhat{\hat r} \def\Rhat{\widehat R} \def\shat{\hat s} \def\Shat{\widehat S} \def\that{\hat t} \def\That{\widehat T} \def\uhat{\hat u} \def\Uhat{\widehat U} \def\vhat{\hat v} \def\Vhat{\widehat V} \def\what{\hat w} \def\What{\widehat W} \def\xhat{\hat x} \def\Xhat{\widehat X} \def\yhat{\hat y} \def\Yhat{\widehat Y} \def\zhat{\hat z} \def\Zhat{\widehat Z} \def\be#1{\begin{equation}\label{ #1}} \def\endeq{\end{equation}} \def\endal{\end{align}} \def\bas{\begin{align*}} \def\eas{\end{align*}} \def\bi{\begin{itemize}} \def\ei{\end{itemize}} \def\eps{\varepsilon} \def\textbf#1{\bf #1} \def\into{\hookrightarrow} \newcommand{\inf}{\infty} \newcommand{\os}[2]{\overset{#1}{#2}} \newcommand{\ms}{(X, \cM, \mu)} \newcommand{\salg}{\sig\text{-algebra}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\bij}{\mathrel{\hookrightarrow\hspace{-1.8ex}\to}} \newcommand{\onto}{\twoheadrightarrow} \newcommand{\id}{\text{id}} \newcommand{\Stab}{\text{Stab}} \def \bl {\backslash} \def \sfin {\sig\text{-finite}} \def \mum {\mu\text{-measurable}} \def \emps {\varnothing} \newcommand{\m}[1]{\boldsymbol{#1}} \newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\Inf}{\text{inf}} \newcommand{\wb}[1]{\overline{#1}} \newcommand{\lto}{\longrightarrow} \newcommand{\todo}[1]{\bf\color{red}{[ToDo] \text{#1}}} \newcommand{\char}[1]{\cX_{#1}} \newcommand{\fp}{f^+} \newcommand{\fm}{f^-} \newcommand{\infm}{\text{inf}} \newcommand{\onorm}[1]{\Norm{#1}_1} \newcommand{\tnorm}[1]{\Norm{#1}_2} \newcommand{\infn}[1]{\Norm{#1}_\inf} \newcommand{\pnorm}[1]{\Norm{#1}_p} \newcommand{\End}{\text{End}} \newcommand{\Ob}{\text{Ob}} \newcommand{\Hom}{\text{Hom}} \newcommand{\intall}{\int_{-\inf}^{\inf}} \newcommand{\intpmpi}{\int_{-\pi}^{\pi}} \newcommand{\div}{\bigr|} \newcommand{\when}{\biggr|} \def \bsp {\begin{split}} \def \esp {\end{split}} \def \bc {\begin{cases}} \def \ec {\end{cases}} \newcommand{\sech}{\text{sech}} \newcommand{\vectk}{\text{Vect}_\text{k}} \newcommand{\top}{\text{Top}} \newcommand{\grp}{\text{Grp}} \newcommand{\pathx}{\text{Paths}_X} \newcommand{\from}{\leftarrow} \newcommand{\lfrom}{\longleftarrow} \newcommand{\tofrom}[2]{\os{\xrightarrow{#1}}{\xleftarrow[#2]{}}} \newcommand{\sym}{\text{Sym}} \newcommand{\Set}{\text{Set}} \newcommand{\zn}{\Z/n\Z} \newcommand{\Mor}{\text{Mor}} \newcommand{\acton}{\circlearrowright} \DeclareMathOperator{\tr}{Tr} \newcommand{\par}{\partial} \newcommand{\Fun}{\text{Fun}} \newcommand{\triv}{\text{triv}} \newcommand{\zmnz}[1]{\Z/{#1}\Z} \newcommand{\tl}{\triangleleft} \newcommand{\paren}[1]{\left({#1}\right)} \newcommand{\ceil}[1]{\lceil{#1}\rceil} \newcommand{\floor}[1]{\lfloor{#1}\rfloor} \newcommand{\mod}{\textrm{mod}} \newcommand{\ndiv}{\nmid} \end{equation} \]

Halo, recently I reacquainted myself with the Sprague-Grundy theorem and would like to introduce the gist of it. I think Wikipedia does a great job explaining the detailed proof, but I would like to fill in some gaps and provide some intuitions. It is recommended to read about the rule of the game of nim (and the wiki page if you are interested in technical details) before reading.

Basically the theorem says that every impartial game is equivalent to a game of nim with a pile of $n$ stones. The number $n$ is called the Grundy number of the impartial game. Now there are two things to explain.

impartial game means that both players of the game have the same set of operations given a fixed position of the game. Chess and Go are not impartial games, because one player can only move or place pieces that have the same color (either black or white).
What does it mean that two games $G$ and $G'$are "equivalent"? One may give a definition stating that if one game has a winning strategy for the player that goes first (or the second player), so does the equivalent game and vice versa. However, having this condition is not enough. Consider any game that has a winning strategy for the second player. Clearly every nim game with non-zero number of stones is equivalent to that game, making Grundy number an ill-defined number. Therefore, we additionally require that the combined games of $G+H$ and $G'+H$ have winning strategies for the same player for any given impartial game $H$.

Now the Sprague-Grundy theorem gives a recursive definition of what the Grundy number of any given impartial game is: Suppose we can go from the current position $G_0$ of the game to $k$ other positions, $\set{G_1, G_2, \dots, G_k}$, and each of $G_i$ is equivalent to the game of nim with $n_i$ stones. Then $G_0$ is equivalent to the game of nim with $n_0$ stones given by \[ n_0 = \text{mex}(n_1, n_2,\dots, n_k) \] Here $\text{mex}(A)$ for some non-negative integer set $A$ is the smallest non-negative integer that is not in $A$.

This is useful, but not that useful, consider a game of nim consists of multiple heaps of stones, where i-th heap has $n_i$ stones. How do we determine the Grundy number and whether we have a winning strategy for the game? If we still use the recursive definition, we will have $\prod n_i$ states to calculate, which can be huge. This is where bit xor operation comes to rescue!

In the following we will consider just one quantity: the xor of all numbers of stones in each heap, i.e. $Q = \bigoplus n_i$. Let's consider the game bottom-up. Which position will the losing player face at the end? Obviously, the position where no stone is left, and $Q = \bigoplus 0 = 0$. It turns out that the winning strategy is to keep leaving the opponent with a position where $Q = 0$! In order to show that, we have to show two things

If right now $Q = 0$, any valid operation will lead to a position where $Q\neq 0$.
If right now $Q\neq 0$, there is always a valid operation that can lead to a position where $Q = 0$

The first statement is easy. Consider you are moving the $k$-th heap. Since we have $Q = (\bigoplus_{i\neq k} n_i) \oplus n_k = 0$, i.e. $\bigoplus_{i\neq k} n_i = n_k$ right now, changing the number of stones in heap $k$ will make $Q$ not equal to 0.

The second statement: First we convert everything into numbers with base of 2 and fill in zeros so that every $n_i$ has the same length. Consider the left-most digit of $Q$ that is not 0, say it is $m$-th digit from the left. Since $Q$ is 1 at $m$, we can pick $n_k$ such that $n_k$ has 1 at that position. Now since $\bigoplus_{i\neq k} n_i$ has 0 at that position, we can set $n_k$ to $\bigoplus_{i\neq k} n_i$. To see that this value is strictly smaller than $n_k$, simply note that both have the same $1$st to $(m-1)$-th digits.

So the winning strategy exists for the first player if we start off with a non-zero $Q$, and for the second player if we start off with $Q = 0$. One more thing: how do we show that the Grundy number is exactly $Q$, instead of any non-zero number in the case of non-zero $Q$? This actually follows from the conclusion of the theorem. Let's consider a simplified case where there are only two heaps. Situations where there are 3 or more heaps can be reduced by merging two of them at a time. Following the notation convention in Wikipedia, we denote a single heap nim game of size $n$ as $\set{*n}$. We want to show that $\set{*a}+\set{*b}\equiv \set{*(a\oplus b)}$, i.e. the combined game of two single heap nim games is equivalent to one single heap nim game in the sense defined in the theorem. From the theorem we know that \[ \set{*a}+\set{*b}\equiv \text{mex}\left(\bigcup_{i = 0}^{a-1} (\set{*i}+\set{*b})\cup\bigcup_{j = 0}^{b-1}(\set{*a}+\set{*j})\right):=\text{mex}(A) \] By induction on $a+b$, we assume that $\set{*i}+\set{*b}\equiv \set{*(i\oplus b)}$ and $+ $ holds. To see that the right hand side is exactly $a\oplus b$, we note that \[ \bsp i\oplus b\oplus a\oplus b &= i\oplus a \neq 0\\ a\oplus j\oplus a\oplus b &= j\oplus b \neq 0\\ i\oplus b\oplus i'\oplus b &= i\oplus i'\\ a\oplus j\oplus a\oplus j' &= j\oplus j' \esp \] i.e. no element in $A$ is equal to $a\oplus b$. Moreover, there are at least $\max(a,b)$ different elements in $A$. The result follows, because $a\oplus b \leq \max(a,b)$. It's left to check the base cases, but they are trivial, so we are done. $\blacksquare$

Now the Grundy theorem is much more practically useful, since it can deal with games that have multiple component games efficiently. Remember that each component game is equivalent to a single heap nim game!

Coding time! Here is a sample problem. Consider the game to be played on interval $[1,100]$, and choosing an interval results in a position that can be split into two component games. For each position we can apply the bit xor operation to get the Grundy number. Applying the mex function to Grundy numbers of all positions gives the answer.

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,n) for(int i = s; i < n; i++)
	
int T; int N; typedef pair<int, int> ii;
vector<ii> intervals;
const int maxn = 105;
int dp[maxn][maxn];


int recur(int st, int end){
	if(st>=end) return dp[st][end] = 0;
	if(dp[st][end]!=-1) return dp[st][end];
	int all[maxn]; memset(all,0,sizeof all);
	for(auto& p : intervals)if(p.first>=st&& p.second<=end){
		int a = recur(st, p.first);
		int b = recur(p.second, end);
		int res = a^b; // merge two component games
		if(res<maxn) all[res] = 1;
	}
	rep(i,0,maxn)if(all[i]==0){ // calculate the mex
		return dp[st][end] = i;
	}
}
	
int main(){
	cin>>T;
	while(T--){
		cin>>N;
		intervals.clear();
		rep(i,0,N) {
			int l,r;cin>>l>>r;
			intervals.push_back({l,r});
		}
		memset(dp, -1, sizeof dp);
		if(recur(1,100)!=0)cout<<"Alice"<<endl;
		else cout<<"Bob"<<endl;
	}
}

Chinese Remainder Theorem

Posted on 2021-07-01 Edited on 2021-07-18

\[ \begin{equation} \def\pr{\text{\rm pr}} \def\sec{\text{\rm sect}} \def\R{\mathbb{R}} \def\N{\mathbb{N}} \def\C{\mathbb{C}} \def\Z{\mathbb{Z}} \def\H{\mathcal{H}} \def\beq{\begin{equation}} \def\endeq{\end{equation}} \def\lesim{\lesssim} \def\mc{\mathcal} \def\h{\mathcal{H}} \newcommand{\bram}[1]{\begin{bmatrix}#1\end{bmatrix}} \def\mn{M^{(n)}} \def\lam{\lambda} \def\wide{\widehat} \def\uk{u^{(k_0)}} \def\uo{u^{(0)}} \def\pj{P^{(2)}} \def\pii{P^{(1)}} \def\pc{P^{Cone}} \def\tx{\tilde x} \DeclareMathOperator{\re}{Re} \DeclareMathOperator{\sgn}{sgn} \def\cplus{c\ci+} \def\cmin{c\ci-} \def\cplusmin{c\ci\pm} \def\chiplus{\chi\ci+} \def\chimin{\chi\ci-} \def\chiplusmin{\chi\ci\pm} \def\psiplus{\psi\ci+} \def\psimin{\psi\ci-} \def\psiplusmin{\psi\ci\pm} \def\sigmaplus{\sigma\ci+} \def\sigmamin{\sigma\ci-} \def\sigmaplusmin{\sigma\ci\pm} \def\bbone{\mathbbm 1} \newcommand{\dil}{\text{\rm Dil}} \newcommand{\spec}{\operatorname{spec}} \newcommand{\ls}{\lesssim} \newcommand{\sL}{\mathscr L} \newcommand{\sJ}{\mathscr J} \newcommand{\sK}{\mathscr K} \newcommand{\wh}{\widehat} \newcommand{\wt}{\widetilde} \newcommand{\A}{\mathcal A} \newcommand{\E}{\mathcal E} \newcommand{\F}{\mathcal F} \newcommand{\D}{\mathcal D} \newcommand{\K}{\mathcal K} \newcommand{\QQ}{\mathcal Q} \newcommand{\RR}{\mathcal R} \newcommand{\f}[2]{\frac{#1}{#2}} \newcommand{\term}{c(z,r)F^\Psi_r(\cdot-z)} \newcommand{\norm}[1]{ \left| #1 \right| } \newcommand{\abs}[1]{ \left| #1 \right| } \newcommand{\Norm}[1]{ \left\| #1 \right\| } \newcommand{\iff}{\Leftrightarrow} \newcommand{\set}[1]{ \left\{ #1 \right\} } \newcommand{\Be}{\begin{equation}} \newcommand{\Ee}{\end{equation}} \newcommand{\Bm}{\begin{multline}} \newcommand{\Em}{\end{multline}} \newcommand{\Bea}{\begin{eqnarray}} \newcommand{\Eea}{\end{eqnarray}} \newcommand{\Beas}{\begin{eqnarray*}} \newcommand{\Eeas}{\end{eqnarray*}} \newcommand{\Benu}{\begin{enumerate}} \newcommand{\Eenu}{\end{enumerate}} \newcommand{\Bi}{\begin{itemize}} \newcommand{\Ei}{\end{itemize}} \def\conv{\text{Conv}} \def\tp{\tilde p} \def\tq{\tilde q} \def\crit{\text{\rm cr}} \def\sparse{\text{\rm sp}} \def\dyad{\text{\rm dyad}} \def\mart{\text{dyad}} \def\intslash{\rlap{\kern .32em $\mspace {.5mu}\backslash$ }\int} \def\qsl{\rlap{\kern .32em $\mspace {.5mu}\backslash$ }\int_{Q_x}} \def\Re{\operatorname{Re\,}} \def\Im{\operatorname{Im\,}} \def\mx \def\mn \def\vth{\vartheta} \def\rn{\rr^{n}} \def\rr{\mathbb R} \def\Q{\mathbb Q} \def\N{\mathbb N} \def\complex{\mathbb C} \def\emph#1{\it #1 } \def\diam{\text{\rm diam}} \def\osc{\text{\rm osc}} \def\ffB{\mathcal B} \def\seq{\subseteq} \def\Ga{\Gamma} \def\ga{\gamma} \def\Th{\Theta} \def\prd{\text{\it prod}} \def\parab{\text{\it parabolic}} \def\eg{\it e.g. } \def\cf{\it cf} \def\Rn{\mathbb R^n} \def\Rd{\mathbb R^d} \def\sgn{\text{\rm sign }} \def\rank{\text{\rm rank }} \def\corank{\text{\rm corank }} \def\coker{\text{\rm Coker }} \def\loc{\text{\rm loc}} \def\spec{\text{\rm spec}} \def\comp{\text{comp}} \def\Coi{C^\infty_0} \def\dist{\text{\it dist}} \def\diag{\text{\rm diag}} \def\supp{text{\rm supp}} \def\rad{\text{\it rad}} \def\sph{\text{sph}} \def\Lip{\text{\rm Lip}} \def\ev{\text{\rm ev}} \def\odd{\text{\rm odd}} \def\inn#1#2{\langle#1,#2\rangle} \def\biginn#1#2{\big\langle#1,#2\big\rangle} \def\rta{\rightarrow} \def\lta{\leftarrow} \def\noi{\noindent} \def\lcontr{\rfloor} \newcommand{\pmtx}[1]{\begin{pmatrix}#1\end{pmatrix}} \def\meas{\text{\rm meas}} \def\card{\text{\rm card}} \def\lc{\lesssim} \def\gc{\gtrsim} \def\pv{\text{\rm p.v.}} \def\a{\alpha} \def\alp{\alpha} \def\Alp{\Alpha} \def\bet{\beta} \def\gam{\gamma} \def\Gam{\Gamma} \def\del{\delta} \def\Del{\Delta} \def\eps{\varepsilon} \def\ep{\epsilon} \def\zet{\zeta} \def\tet{\theta} \def\Tet{\Theta} \def\iot{\iota} \def\kap{\kappa} \def\ka{\kappa} \def\lam{\lambda} \def\Lam{\Lambda} \def\la{\lambda} \def\La{\Lambda} \def\sig{\sigma} \def\Sig{\Sigma} \def\si{\sigma} \def\Si{\Sigma} \def\vphi{\varphi} \def\ome{\omega} \def\Ome{\Omega} \def\om{\omega} \def\fA{\mathfrak {A}} \def\fB{\mathfrak {B}} \def\fC{\mathfrak {C}} \def\fD{\mathfrak {D}} \def\fE{\mathfrak {E}} \def\fF{\mathfrak {F}} \def\fG{mathfrak {G}} \def\fH{\mathfrak {H}} \def\fI{\mathfrak {I}} \def\fJ{\mathfrak {J}} \def\fK{\mathfrak {K}} \def\fL{\mathfrak {L}} \def\fM{\mathfrak {M}} \def\fN{\mathfrak {N}} \def\fO{\mathfrak {O}} \def\fP{\mathfrak {P}} \def\fQ{\mathfrak {Q}} \def\fR{\mathfrak {R}} \def\fS{\mathfrak {S}} \def\fT{\mathfrak {T}} \def\fU{\mathfrak {U}} \def\fV{\mathfrak {V}} \def\fW{\mathfrak {W}} \def\fX{\mathfrak {X}} \def\fY{\mathfrak {Y}} \def\fZ{\mathfrak {Z}} \def\fa{\mathfrak {a}} \def\fb{\mathfrak {b}} \def\fc{\mathfrak {c}} \def\fd{\mathfrak {d}} \def\fe{\mathfrak {e}} \def\ff{\mathfrak {f}} \def\fg{\mathfrak {g}} \def\fh{\mathfrak {h}} \def\fj{\mathfrak {j}} \def\fk{\mathfrak {k}} \def\fl{\mathfrak {l}} \def\fn{\mathfrak {n}} \def\fo{\mathfrak {o}} \def\fq{\mathfrak {q}} \def\fr{\mathfrak {r}} \def\fs{\mathfrak {s}} \def\ft{\mathfrak {t}} \def\fu{\mathfrak {u}} \def\fv{\mathfrak {v}} \def\fw{\mathfrak {w}} \def\fx{\mathfrak {x}} \def\fy{\mathfrak {y}} \def\fz{\mathfrak {z}} \def\bbA{\mathbb {A}} \def\bbB{\mathbb {B}} \def\bbC{\mathbb {C}} \def\bbD{\mathbb {D}} \def\bbE{\mathbb {E}} \def\bbF{\mathbb {F}} \def\bbG{\mathbb {G}} \def\bbH{\mathbb {H}} \def\bbI{\mathbb {I}} \def\bbJ{\mathbb {J}} \def\bbK{\mathbb {K}} \def\bbL{\mathbb {L}} \def\bbM{\mathbb {M}} \def\bbN{\mathbb {N}} \def\bbO{\mathbb {O}} \def\bbP{\mathbb {P}} \def\bbQ{\mathbb {Q}} \def\bbR{\mathbb {R}} \def\bbS{\mathbb {S}} \def\bbT{\mathbb {T}} \def\bbU{\mathbb {U}} \def\bbV{\mathbb {V}} \def\bbW{\mathbb {W}} \def\bbX{\mathbb {X}} \def\bbY{\mathbb {Y}} \def\bbZ{\mathbb {Z}} \def\cA{\mathcal {A}} \def\cB{\mathcal {B}} \def\cC{\mathcal {C}} \def\cD{\mathcal {D}} \def\cE{\mathcal {E}} \def\cF{\mathcal {F}} \def\cG{\mathcal {G}} \def\cH{\mathcal {H}} \def\cI{\mathcal {I}} \def\cJ{\mathcal {J}} \def\cK{\mathcal {K}} \def\cL{\mathcal {L}} \def\cM{\mathcal {M}} \def\cN{\mathcal {N}} \def\cO{\mathcal {O}} \def\cP{\mathcal {P}} \def\cQ{\mathcal {Q}} \def\cR{\mathcal {R}} \def\cS{\mathcal {S}} \def\cT{\mathcal {T}} \def\cU{\mathcal {U}} \def\cV{\mathcal {V}} \def\cW{\mathcal {W}} \def\cX{\mathcal {X}} \def\cY{\mathcal {Y}} \def\cZ{\mathcal {Z}} \def\tA{\widetilde{A}} \def\tB{\widetilde{B}} \def\tC{\widetilde{C}} \def\tD{\widetilde{D}} \def\tE{\widetilde{E}} \def\tF{\widetilde{F}} \def\tG{\widetilde{G}} \def\tH{\widetilde{H}} \def\tI{\widetilde{I}} \def\tJ{\widetilde{J}} \def\tK{\widetilde{K}} \def\tL{\widetilde{L}} \def\tM{\widetilde{M}} \def\tN{\widetilde{N}} \def\tO{\widetilde{O}} \def\tP{\widetilde{P}} \def\tQ{\widetilde{Q}} \def\tR{\widetilde{R}} \def\tS{\widetilde{S}} \def\tT{\widetilde{T}} \def\tU{\widetilde{U}} \def\tV{\widetilde{V}} \def\tW{\widetilde{W}} \def\tX{\widetilde{X}} \def\tY{\widetilde{Y}} \def\tZ{\widetilde{Z}} \def\tcA{\widetilde{\mathcal {A}}} \def\tcB{\widetilde{\mathcal {B}}} \def\tcC{\widetilde{\mathcal {C}}} \def\tcD{\widetilde{\mathcal {D}}} \def\tcE{\widetilde{\mathcal {E}}} \def\tcF{\widetilde{\mathcal {F}}} \def\tcG{\widetilde{\mathcal {G}}} \def\tcH{\widetilde{\mathcal {H}}} \def\tcI{\widetilde{\mathcal {I}}} \def\tcJ{\widetilde{\mathcal {J}}} \def\tcK{\widetilde{\mathcal {K}}} \def\tcL{\widetilde{\mathcal {L}}} \def\tcM{\widetilde{\mathcal {M}}} \def\tcN{\widetilde{\mathcal {N}}} \def\tcO{\widetilde{\mathcal {O}}} \def\tcP{\widetilde{\mathcal {P}}} \def\tcQ{\widetilde{\mathcal {Q}}} \def\tcR{\widetilde{\mathcal {R}}} \def\tcS{\widetilde{\mathcal {S}}} \def\tcT{\widetilde{\mathcal {T}}} \def\tcU{\widetilde{\mathcal {U}}} \def\tcV{\widetilde{\mathcal {V}}} \def\tcW{\widetilde{\mathcal {W}}} \def\tcX{\widetilde{\mathcal {X}}} \def\tcY{\widetilde{\mathcal {Y}}} \def\tcZ{\widetilde{\mathcal {Z}}} \def\tfA{\widetilde{\mathfrak {A}}} \def\tfB{\widetilde{\mathfrak {B}}} \def\tfC{\widetilde{\mathfrak {C}}} \def\tfD{\widetilde{\mathfrak {D}}} \def\tfE{\widetilde{\mathfrak {E}}} \def\tfF{\widetilde{\mathfrak {F}}} \def\tfG{\widetilde{\mathfrak {G}}} \def\tfH{\widetilde{\mathfrak {H}}} \def\tfI{\widetilde{\mathfrak {I}}} \def\tfJ{\widetilde{\mathfrak {J}}} \def\tfK{\widetilde{\mathfrak {K}}} \def\tfL{\widetilde{\mathfrak {L}}} \def\tfM{\widetilde{\mathfrak {M}}} \def\tfN{\widetilde{\mathfrak {N}}} \def\tfO{\widetilde{\mathfrak {O}}} \def\tfP{\widetilde{\mathfrak {P}}} \def\tfQ{\widetilde{\mathfrak {Q}}} \def\tfR{\widetilde{\mathfrak {R}}} \def\tfS{\widetilde{\mathfrak {S}}} \def\tfT{\widetilde{\mathfrak {T}}} \def\tfU{\widetilde{\mathfrak {U}}} \def\tfV{\widetilde{\mathfrak {V}}} \def\tfW{\widetilde{\mathfrak {W}}} \def\tfX{\widetilde{\mathfrak {X}}} \def\tfY{\widetilde{\mathfrak {Y}}} \def\tfZ{\widetilde{\mathfrak {Z}}} \def\Atil{\widetilde A} \def\atil{\tilde a} \def\Btil{\widetilde B} \def\btil{\tilde b} \def\Ctil{\widetilde C} \def\ctil{\tilde c} \def\Dtil{\widetilde D} \def\dtil{\tilde d} \def\Etil{\widetilde E} \def\etil{\tilde e} \def\Ftil{\widetilde F} \def\ftil{\tilde f} \def\Gtil{\widetilde G} \def\gtil{\tilde g} \def\Htil{\widetilde H} \def\htil{\tilde h} \def\Itil{\widetilde I} \def\itil{\tilde i} \def\Jtil{\widetilde J} \def\jtil{\tilde j} \def\Ktil{\widetilde K} \def\ktil{\tilde k} \def\Ltil{\widetilde L} \def\ltil{\tilde l} \def\Mtil{\widetilde M} \def\mtil{\tilde m} \def\Ntil{\widetilde N} \def\ntil{\tilde n} \def\Otil{\widetilde O} \def\otil{\tilde o} \def\Ptil{\widetilde P} \def\ptil{\tilde p} \def\Qtil{\widetilde Q} \def\qtil{\tilde q} \def\Rtil{\widetilde R} \def\rtil{\tilde r} \def\Stil{\widetilde S} \def\stil{\tilde s} \def\Ttil{\widetilde T} \def\ttil{\tilde t} \def\Util{\widetilde U} \def\util{\tilde u} \def\Vtil{\widetilde V} \def\vtil{\tilde v} \def\Wtil{\widetilde W} \def\wtil{\tilde w} \def\Xtil{\widetilde X} \def\xtil{\tilde x} \def\Ytil{\widetilde Y} \def\ytil{\tilde y} \def\Ztil{\widetilde Z} \def\ztil{\tilde z} \def\ahat{\hat a} \def\Ahat{\widehat A} \def\bhat{\hat b} \def\Bhat{\widehat B} \def\chat{\hat c} \def\Chat{\widehat C} \def\dhat{\hat d} \def\Dhat{\widehat D} \def\ehat{\hat e} \def\Ehat{\widehat E} \def\fhat{\hat f} \def\Fhat{\widehat F} \def\ghat{\hat g} \def\Ghat{\widehat G} \def\hhat{\hat h} \def\Hhat{\widehat H} \def\ihat{\hat i} \def\Ihat{\widehat I} \def\jhat{\hat j} \def\Jhat{\widehat J} \def\khat{\hat k} \def\Khat{\widehat K} \def\lhat{\hat l} \def\Lhat{\widehat L} \def\mhat{\hat m} \def\Mhat{\widehat M} \def\nhat{\hat n} \def\Nhat{\widehat N} \def\ohat{\hat o} \def\Ohat{\widehat O} \def\phat{\hat p} \def\Phat{\widehat P} \def\qhat{\hat q} \def\Qhat{\widehat Q} \def\rhat{\hat r} \def\Rhat{\widehat R} \def\shat{\hat s} \def\Shat{\widehat S} \def\that{\hat t} \def\That{\widehat T} \def\uhat{\hat u} \def\Uhat{\widehat U} \def\vhat{\hat v} \def\Vhat{\widehat V} \def\what{\hat w} \def\What{\widehat W} \def\xhat{\hat x} \def\Xhat{\widehat X} \def\yhat{\hat y} \def\Yhat{\widehat Y} \def\zhat{\hat z} \def\Zhat{\widehat Z} \def\be#1{\begin{equation}\label{ #1}} \def\endeq{\end{equation}} \def\endal{\end{align}} \def\bas{\begin{align*}} \def\eas{\end{align*}} \def\bi{\begin{itemize}} \def\ei{\end{itemize}} \def\eps{\varepsilon} \def\textbf#1{\bf #1} \def\into{\hookrightarrow} \newcommand{\inf}{\infty} \newcommand{\os}[2]{\overset{#1}{#2}} \newcommand{\ms}{(X, \cM, \mu)} \newcommand{\salg}{\sig\text{-algebra}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\bij}{\mathrel{\hookrightarrow\hspace{-1.8ex}\to}} \newcommand{\onto}{\twoheadrightarrow} \newcommand{\id}{\text{id}} \newcommand{\Stab}{\text{Stab}} \def \bl {\backslash} \def \sfin {\sig\text{-finite}} \def \mum {\mu\text{-measurable}} \def \emps {\varnothing} \newcommand{\m}[1]{\boldsymbol{#1}} \newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\Inf}{\text{inf}} \newcommand{\wb}[1]{\overline{#1}} \newcommand{\lto}{\longrightarrow} \newcommand{\todo}[1]{\bf\color{red}{[ToDo] \text{#1}}} \newcommand{\char}[1]{\cX_{#1}} \newcommand{\fp}{f^+} \newcommand{\fm}{f^-} \newcommand{\infm}{\text{inf}} \newcommand{\onorm}[1]{\Norm{#1}_1} \newcommand{\tnorm}[1]{\Norm{#1}_2} \newcommand{\infn}[1]{\Norm{#1}_\inf} \newcommand{\pnorm}[1]{\Norm{#1}_p} \newcommand{\End}{\text{End}} \newcommand{\Ob}{\text{Ob}} \newcommand{\Hom}{\text{Hom}} \newcommand{\intall}{\int_{-\inf}^{\inf}} \newcommand{\intpmpi}{\int_{-\pi}^{\pi}} \newcommand{\div}{\bigr|} \newcommand{\when}{\biggr|} \def \bsp {\begin{split}} \def \esp {\end{split}} \def \bc {\begin{cases}} \def \ec {\end{cases}} \newcommand{\sech}{\text{sech}} \newcommand{\vectk}{\text{Vect}_\text{k}} \newcommand{\top}{\text{Top}} \newcommand{\grp}{\text{Grp}} \newcommand{\pathx}{\text{Paths}_X} \newcommand{\from}{\leftarrow} \newcommand{\lfrom}{\longleftarrow} \newcommand{\tofrom}[2]{\os{\xrightarrow{#1}}{\xleftarrow[#2]{}}} \newcommand{\sym}{\text{Sym}} \newcommand{\Set}{\text{Set}} \newcommand{\zn}{\Z/n\Z} \newcommand{\Mor}{\text{Mor}} \newcommand{\acton}{\circlearrowright} \DeclareMathOperator{\tr}{Tr} \newcommand{\par}{\partial} \newcommand{\Fun}{\text{Fun}} \newcommand{\triv}{\text{triv}} \newcommand{\zmnz}[1]{\Z/{#1}\Z} \newcommand{\tl}{\triangleleft} \newcommand{\paren}[1]{\left({#1}\right)} \newcommand{\ceil}[1]{\lceil{#1}\rceil} \newcommand{\floor}[1]{\lfloor{#1}\rfloor} \newcommand{\mod}{\textrm{mod}} \newcommand{\ndiv}{\nmid} \end{equation} \]

I recently decided to pick up competitive programming, not only because I enjoy programming, but also because this is a fail safe for my academic career. With the tension between China and US rises, any Chinese research personnel in the US is bound to be persecuted in one way or another (it already begins with the visa application). It will be increasingly risky to put all the eggs in one basket. And the recent Wenhua Jiang Incident further dims the light on the path to tenure in China for many researchers. So in short, doing competitive programming is an act of interest (pun intended).

So much gibberish, today we are going to talk about Chinese Remainder Theorem, which basically says that given a set of coprime integers, and we know the remainders of an unknown integer modulo those coprime numbers, then the smallest such unknown number can be uniquely determined. For a rigorous definition, see wiki. The proof is quite simply, say the set of coprime numbers are $n_1, n_2, \dots, n_k$, and $N = \Pi_i n_i$. And the aforementioned remainders are $r_1, r_2, \dots, r_k$. We only consider integers in the range $[1, N]$. The key observation is that if two different numbers have the same set of remainders, the absolute difference between them will be divisible by all $n_i$ s, and since the difference is capped by $N-1$, it is zero, contradiction! Therefore a one-to-one correspondence can be established between each integer within that range and a set of all possible remainders. Note that the range of each $r_i$ is $[0, r_i-1]$, so both sides have the same cardinality.

Now let's look at implementation of this theorem in competitive programming. An example problem is here. So the problem is to solve the following set of congruence equations \[ x \equiv a_1 \pmod{m_1}\\ x\equiv a_2 \pmod{m_2} \] which is equivalent to \[ x = a_1+n_1 m_1 = a_2+n_2m_2 \] for some integer $n_1$ and $n_2$, i.e. \[ \beq a_2 - a_1 = n_1m_1 - n_2m_2 \tag{1} \label{eq:1} \end{equation} \] We can use extended Euclidean algorithm to solve for $n_i$ given $m_i$ in the following equation \[ \beq n_1m_1 - n_2m_2 = \gcd(m_1, m_2) := d \tag{2}\label{eq:2} \endeq \] Detour (please skip at will): There is a proof of existence of an integer solution that I really like about the above equation. Since we can divide both sides by $\gcd(m_1, m_2)$, we can just deal with the case $n_1m_1 - n_2m_2 = 1$ where $m_1$ and $m_2$ are coprime to each other. Now here is the clever proof: Let $r$ be the smallest positive integer such that $n_1m_1 - n_2m_2 = r$ has an integer solution. And we can express $m_1$ as multiple of $r$ plus a remainder term, i.e. $m_1 = q_1r+r_1$. So the equation becomes \[ n_1m_1 - n_2m_2 = r = (m_1 - r_1)/q_1 \] Some algebra shows that $(1-q_1n_1)m_1+n_2q_1m_2 = r_1$, note that $r_1$, as a remainder of division by $r$, is strictly smaller than $r$. So there is only one possibility: $r_1 = 0$. So $m_1$ is actually a multiple of $r$ ! By symmetry, $m_2$ is a multiple of $r$ as well. However since $m_1$ and $m_2$ are coprime, $r $ can only be 1. Note that this is effectively a proof of existence since such smallest $r$ must exist as everything here is finite. $\blacksquare$

Now if $d\ndiv a_1 - a_2$, then we can already claim that the pair of congruent equations have no solution. If otherwise, we can multiply both sides of $\eqref{eq:2}$ by $(a_2 - a_1)/d$ to get $\eqref{eq:1}$. For equation sets that contain 3 or more equations, we can process and merge two of them at a time

Coding time!

typedef long long ll;
//extended euler's algorithm
void gcd(ll a, ll b, ll& d, ll& x, ll& y){
	if(!b){d  = a; x = 1; y = 0;}
	else {gcd(b, a%b, d, y, x); y -= (a/b)*x;}
}

ll china(int n, ll* a, ll* m){
	ll d,y,x = 0;
	rep(i,0,n-1){
		gcd(m[i],m[i+1],d,x,y);
		if((a[i+1] - a[i])%d!=0) return -1;
		a[i+1] = a[i]+((x*((a[i+1] - a[i])/d))%(m[i+1]/d))*m[i];
		m[i+1] = m[i]*(m[i+1]/d);
		a[i+1] = a[i+1]%m[i+1];
	}
	ll M = m[n-1];
	return (a[n-1]+M)%M;
}

The extended Euler's algorithm can be implemented by just two lines of C++, pretty surprising, isn't it? One last thing to note, as there is a 10^18 numeric limit in most competitive programming contest, we need to handle the overflow problem using $c(a\pmod{b})\equiv ca \pmod{cb}$ in the following line of code

1	a[i+1] = a[i]+((x((a[i+1] - a[i])/d))%(m[i+1]/d))m[i];

That's it, happy coding until next time!

Reference

[Tutorial] Chinese Remainder Theorem - Codeforces