中国剩余定理
不定方程 \(ax+by = gcd(a,b)\)的解
先用扩展欧几里得算法求得不定方程的一组特解：\(x_0,y_0\)
则不定方程的通解为
\[ \left\{\begin{matrix} x = x_0 - \frac{k\; * \; b}{d} \\ y = y_0 + \frac{k\; * \; a}{d} \end{matrix}\right. \; k \; \epsilon \; Z \](\(d\)指的是\(gcd(a,b)\))
acwing204.表达整数的奇怪方式
题目：给定 2n 个整数 \(a_1,a_2,…,a_n\) 和 \(m1,m2,…,m_n，\)求一个最小的非负整数 x，满足 \(∀i∈[1,n],x≡m_i(mod\; a_i)\)。
思路
虽然和中国剩余定理一样这里都是一元线性同余方程组
\[(s) = \left\{\begin{matrix} x \equiv m_1 (mod\; a_1) \\x \equiv m_2 (mod\; a_2) \\ ... \\ ... \\ x \equiv m_n(mod\; a_n) \end{matrix}\right. \]可以发现并没有说明\(m_1,m_2...\)两两互质，所以不能直接使用中国剩余定理
我们需要自己推导一下，看看应该怎么写。
这个方程组可以写成
\[\left\{\begin{matrix} x\; mod\; a_1 = m_1 \\ x\; mod\; a_2 = m_2 \\ ... \\ ... \\ x\; mod\; a_n = m_n \end{matrix}\right. \]即
\[\left\{\begin{matrix} x = k_1 * a_1 + m_1 \\ x = k_2 * a_2 + m_2 \\ ... \\ ... \\ x = k_n * a_n + m_n \end{matrix}\right. \]先看前两个式子
\[\left\{\begin{matrix} x = k_1 * a_1 + m_1 \;① \\ x = k_2 * a_2 + m_2 \;② \end{matrix}\right. \;\; 有\;k_1 * a_1 + m_1 = k_2 * a_2 + m_2 \]写成不定方程为 \(k_1 * a_1 - k_2 * a_2 = m_2 - m_1\)
若 \((a_1,a_2)|(m_2-m_1)\)则方程有解
若不能整除则方程无解
若方程有解，先用扩展欧几里得算法求出一个特解\(k_1,k_2\)
则该方程组存在通解
所以
\[x = k_1' * a_1 + m_1 \\ = (k_1 + \frac{k\; * \; a_2}{d}) * a_1 + m_1 \\ = k_1 * a_1 + m_1 + k * \frac{a_1\; * \; a_2}{d} \\ = x_0 + k * lcm(a1,a2) \;\;把lcm(a_1,a_2)记作a \\ = x_0 + k * a \]至此由公式①②推出来了 $ x = x_0 + k * a$
所以这n个公式两两联立推n-1次就可以得到最终一个方程 \(x = k * a + x_0\)
(\(x_0\)在计算过程中可以计算出来)
\(x = k * a + x_0\) 我们求\(x\)最小是多少，就相当于求\(x \; mod \; a ≡ x_0\) 的最小正整数解，即可以求 \(x_0 \; mod \; a\)的正余数(在模a的移一下，\(x\)和\(x_0\)是相等的)
即求 \((x_0 \;mod\; a + a)\;mod\;a\) 因为c++中余数可能为负，所以在第一次%完之后加上a一定为正，再模a就可以了
思路总结
每次将两个式子合并成一个式子
对合并的式子\(k_1 * a_1 - k_2 * a_2 = m_2 - m_1\)使用扩展欧几里得算法求一个特解，求出 \(k_1,k_2\)
如果\((m_2-m_1)\)不是\(gcd(a_1,a_2)\)的整数倍则无解
把\(k_1\)变成原来的\((m_2-m_1)/d\)倍(扩展欧几里得算法求出的\(k_1\)是\(k_1 * a_1 - k_2 * a_2 = gcd(a_1,a_2)\)的解，这里要变成原公式的解)
根据不定方程通解公式\(k_1' = k_1 + \frac{k\; * \; a_2}{d}\)更新\(k_1\)为最小的解(要取模正余数)
\(k_1 * a_1 + m_1\)变成新式子的\(m_1\)，也是\(x_0\)
\(lcm(a_1,a_2)\)变成新式子的\(a_1\),取正的最小公倍数(比如一个-2,一个-4他们最小公倍数如果是负的就可以无限小，这里要取正的)
最后的结果就是\(x_0 \; mod \; a\)的正余数即(x0 % a + a) % a
代码