流下了不会数学的眼泪
中国剩余定理(CRT)
内容
中国剩余定理给出了以下的一元线性同余方程组：
$$
\begin{Bmatrix}
x\equiv a_1 (\mod m1 )\
x\equiv a_2 (\mod m2 )\
· · · · \
· · · · \
x\equiv a_2 (\mod m3 )\
\end{Bmatrix}
$$
中国剩余定理说明：假设整数$m_1,m_2, … ,m_n$两两互质，则对任意的整数：$a_1,a_2, … ,a_n$，方程组有解，在$\mod M$ 下解是唯一的
结论
$$
令\ M = m_1·m_2·m_3···m_n
$$
$$
则\ x= (\sum_{i=1}^{n}{a_i} · \frac {M}{m_i} · inv(\frac {M}{m_i},m_i)) \% M
$$
其中$inv(\frac {M}{m_i},m_i)$为$\frac {M}{m_i}$在$ \mod m_i$意义下的逆元
欧几里德
内容
解决求 $gcd(a,b)$
线段上格点(整数点)的个数 (gcd)
答案
$$
gcd(|x_1-x_2|，|y_1-y2|)-1
$$
证明
令$x=|x_1-x_2|，y=|y_1-y2|$
则 $d=gcd(x，y)$，即$x$和$y$可以分成$d$份，每份为$(x/d，y/d)$ 且 $x/d，y/d$ 都为整数，并且$y/x$比值不变
扩展欧几里德
内容
已知 $a,b$ 求解一组 $x,y$，使它们满足贝祖等式： $ax+by = gcd(a, b) =d$ ( 解一定存在 )
通解
前提a!=0且b!=0，使用扩展欧几里德解出的一组特解$x_0，y_0$后，可推出通解：
$$
x=x_0+k·b/\gcd(a,b)
$$
$$
y=y_0-k·a/\gcd(a,b)
$$简单证明：
考虑给$ax+by = gcd(a, b) =d$，ax项增加，bx减少，但和不变，这一项最小就是 $lcm(a,b)$