EXGCD和EXCRT前言我与这两个算法有很深的渊源。第一次遇到是三年前的五校联考，\(\text{t1}\)需要用到，于是我成了全场唯一一个没切\(\text{t1}\)的。第二次是两年前湖南省集，我依稀记得这是第二场的\(\text{Day1T2}\)，我花了\(\text{2.5h}\)去推\(\text{exCRT}\)的式子

Exgcd和Excrt的一些推导ExgcdExgcd是用来求解二元一次不定方程的算法，即\[ax+by=c\]根据贝祖定理，该方程有解当且仅当\(\gcd(a,b)\midc\)，所以只用求解\[ax+by=\gcd(a,b)\]又因为\[\gcd(a,b)=\gcd(b,a\bmodb)\]可以先求解\[bx'+(a\bmodb)y'=\gcd(a,b)\]变形得\[

传送门显然每一只龙对应了唯一的一把剑。用multiset可以求出每一把剑。于是题目就变成了：\[\begin{cases}b_1x\equiva_1\pmod{m_1}\\b_2x\equiva_2\pmod{m_2}\\\dots\\b_nx\equiva_n\pmod{m_n}\end{cases}\]如果\(b_i=1\)，直接EXCRT即可。现在\(b_i>1\)，还是以EXCRT

普通的CRT只能处理模数两两互质的情况，而EXCRT可以求得任意情况下同余方程组的通解。思想：把两个同余方程合并成一个，直到剩下一个。考虑两个同余方程\(x\equivp_1\pmod{m_1},x\equivp_2\pmod{m_2}\)。则\(x=p_1+m_1A=p_2+m_2B\)。移项得\(m_1A-m_2B=p_2-p_1\)。这是

扩展中国剩余定理（excrt）本来应该先学中国剩余定理的。但是有了扩展中国剩余定理，朴素的CRT就没用了。扩展中国剩余定理用来求解如下形式的同余方程组：\[\begin{cases}x\equiva_1\({\rmmod}\b_1)\\x\equiva_2\({\rmmod}\b_2)\\...\\x\equiva_n\({\rmmod}\b_

一、CRT1.前置芝士exgcd2.应用范围求解同余方程组：\[\begin{cases}x\equiva_1\modm_1\\x\equiva_2\modm_2\\x\equiva_3\modm_3\\~~~~~~~~~~~~~\vdots\\x\equiva_k\modm_k\end{cases}\]其中\(~m_1,m_2,m_3,\cdots,m_k~\)两两互质3.算法原理考虑构造一组解：记

由于exCRT完美的平替了CRT的全部功能，故不再详细复习CRT的相关内容.考虑如下同余方程组，\[\begin{cases}x\equiva_1\pmod{m_1}\\x\equiva_2\pmod{m_2}\\\end{cases}\]展开得，\[a_1+k_1\timesm_1=a_2+k_2\timesm_2\]\[\Rightarrowk_1\timesm_1-k_2\ti

中国剩余定理(CRT)不能解决模数不互质情况的模线性同余方程组。这是中国剩余定理的原理所决定的。但当我们的模数不互质时，这个方式显然就寄掉了，因此我们要打破原有的思路，去找一个新的方式解不定方程组，这时我们的扩展中国剩余定理（EXCRT）就出现了假设我们现在有如下不定方程组\[\b

CF338DGCDTable个人评价：还好算法扩展CRT题面给了一张\(n\timesm\)的矩阵，第i行j列的权值是gcd(i,j),现在有一个长度为k的序列A，问是否存在(i,j)使得\(gcd(i,j+l-1)=a_l(1\leql\leqk)\)问题分析我们将对应行设为x,对应列设为y，那么就有如下同余方程组\(x\equiv(y+l-1)

众所周知CRT只能处理模数两两互质的情况，因为它要算逆元。那么如果模数两两不互质，有没有办法呢？答案是有的。我们先来考虑两个同余方程，设为\(x\equivb_1\pmod{a_1},x\e

扩展中国剩余定理讲解扩展之前，我们先叙述一下普通的中国剩余定理中国剩余定理中国剩余定理通过一种非常精巧的构造求出了一个可行解但是毕竟是构造，所以相对较复杂\[

\[\begin{aligned}&\begin{cases}x\equiva_1\pmod{m_1}\\x\equiva_2\pmod{m_2}\end{cases}\\&x=pm_1+a_1=qm_2+a_2\\&pm_1-qm_2=a_2-a_1\end{aligned}\]将其视为

中国剩余定理-模数之间两两互质点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;//中国剩余定理CRTinta[200000];intr[200000];

求解同余方程组最小整数解：\[\left\{\begin{matrix}x\equiva_1\pmod{m_1}\\x\equiva_2\pmod{m_2}\\\cdots\\x\equiva_n\pmod{m_n}\end{matrix}\right.\]设

其实这道题的主体并不难，主要是细节很多我们可以把题目分成界限分明的两部分，第一部分，屠每条龙所用的剑只和当前拥有的剑有关。于是可以单独开一个数据结构按题目维护。另

求解如下形式的一元线性同余方程组（其中\(n_1,n_2,···,n_k\)不两两互质）\[\left\{ \begin{matrix}x&\equiv&a_1&(mod\n_1)\\ x&\equiv&a_2&(mod