Math-Review 2019-07-02

  • gcd,exgcd

    求解\(ax+by= (a,b)\) \[ \begin{aligned} gcd(a,b)&= gcd(b,a\%b) \pmod p\\ ax+by&= bx+(a-\lfloor\frac{a}{b}\rfloor b)y\\ ax+by&= ay+b(x-\lfloor\frac{a}{b}\rfloor y) \\ &\to x=y,y=(x-\lfloor\frac{a}{b}\rfloor y) \end{aligned} \] \(ax+by\equiv (a,b)\)的下一组解 \[ a\left(x+\frac{b}{(a,b)}\right)+b\left(y-\frac{a}{(a,b)}\right)= (a,b) \]

\[ \left\{\begin{matrix} x=a_1 \pmod{m_1}\\ x=a_2 \pmod{m_2}\\ x=a_3 \pmod{m_3}\\ ...\\ x=a_n \pmod{m_n}\\ \end{matrix}\right. \]

\(m\)两两互质,求最小的符合条件的\(x\)

定义\(M=\prod m_i\)\(M_i=\frac{M}{m_i}\)\(iM_i=\frac{1}{M_i} \pmod{m_i}\) \[ x\equiv \sum_{i=1}^{n}a_i\times M_i\times iM_i \pmod M \]

这个方程组,有通解\(x'\equiv x+lcm(m_1,m_2,..,m_n)\times i (i \in \Z)\),即\(x'\equiv x \pmod{lcm(m_1,m_2,…m_n)}\)

对于前\(i-1\)个等式求出了答案为\(x\),考虑合并第\(i\)个等式,即要求出一个\(x'\)满足 \[ \left\{\begin{matrix} x'\equiv x& \pmod{lcm(m_1,m_2,…m_{i-1})}\\ x'\equiv a_i& \pmod{m_i} \end{matrix}\right. \]

也就是\(x+i\times lcm(m_1,m_2,..m_{i-1})\equiv a_i \pmod{m_i}\),可以用exgcd求解。