EXCRT

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

一、CRT 1. 前置芝士 exgcd 2. 应用范围 求解同余方程组： \[\begin{cases}x\equiv a_1\mod m_1\\x\equiv a_2\mod m_2\\x\equiv a_3\mod m_3\\~~~~~~~~~~~~~\vdots\\x\equiv a_k\mo ......

# 7.29 数论 WIP $a\equiv b\pmod p\Rightarrow \frac{a}{d}\equiv \frac{b}{d}\pmod{\frac{p}{d}},d=\gcd(a,b,p)$。 ## exGCD 1. 若 $(a,b)=1$，则 $0\leq xb\to a\bm ......

由于exCRT完美的平替了CRT的全部功能，故不再详细复习CRT的相关内容. 考虑如下同余方程组， $$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \end{cases} $$ 展开得， $$a_1 + k_ ......

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

CF338D GCD Table 个人评价：还好 算法 扩展CRT 题面 给了一张$n\times m$的矩阵，第i行j列的权值是gcd(i,j),现在有一个长度为k的序列A，问是否存在(i,j)使得$gcd(i,j+l-1)=a_l(1\leq l\leq k)$ 问题分析 我们将对应行设为x,对 ......

problem 求这个关于 $x$ 的方程组的最小正整数解： $$\begin{cases} x\equiv b_1 \pmod{a_1}\ x\equiv b_2 \pmod{a_2}\ x\equiv b_3 \pmod{a_3}\ \cdots\ x\equiv b_n \pmod{a_n}\ ......