很久之前写的……有很多错误。现在赶紧更新一波……
1.扩展欧几里得算法：求解不定方程 (a * x + b * y = m)。
首先，当 (m) 为 (gcd(a, b)) 的倍数时，方程有整数解；否则无整数解。
证明：首先如果不满足此条件，一定不会有整数解。此处显然无须赘述。若 (p*x + q*y = gcd(p, q)) 存在解，那么 (a*x + b*y = c) 存在解。因为可以将式子左右两边同除 (gcd(a, b))，那么此时有 (a_{1} * x + b_{1} * y = c_{1})。而此时 (gcd(a_{1}, b_{1}) = 1)。所以在求得了 (a_{1} * x + b_{1} * y = 1) 之后，我们可以同时给方程的两边乘上 (c _{1}) 。
所以问题转化为：如何证明 (p * x + q * y = gcd(p, q)) 存在解？两边同除 (gcd(p, q)) 得到 (a * x + b * y = 1)（(gcd(a, b) = 1)）。
根据欧几里得算法我们有 (gcdleft ( a,b ight ) = gcdleft ( b,a mod b ight ))
我们若能求出 (b * x' + left ( a mod b ight ) * y' = gcd(a, b))，
则：(b * x' + left ( a mod b ight ) * y')
( = a * y' + b * left ( x' - left ( frac{a}{b} ight )* y' ight ))
(=gcdleft ( a,b ight ))；
又因为(gcd(a, b) = 1)，
所以得出：(x = y', y = x' - left ( frac{a}{b} ight )* y')；
在代码实现上可以递归求解：
void exgcd(int a, int b, int &x, int &y) { if(!b) { x = 1, y = 0; return; } exgcd(b, a % b, x, y); ll tem = x; x = y; y = tem - a / b * y; }
在我们获得了不定方程的一组解(left ( x_{0},y_{0} ight ))之后，则不定方程的任何一组解满足 ：(Delta x = frac{m * b}{gcdleft ( a,b ight )}, Delta y = frac{m * a}{gcdleft ( a,b ight )})。
扩展欧几里得算法一个非常常见的应用即为：求乘法逆元。
2.同余方程：
求解形如 (a * xequiv b left ( mod m ight ) ) 的方程。其实我并不是很会同余方程，但有两个定理还是非常重要的：
若(gcdleft ( a,b ight )=1)，则方程(axequiv c left ( mod b ight )) 在 (left [ 0, b - 1 ight ])上有唯一解。
若(gcdleft ( a,b ight )=d, d|c)，则方程(axequiv c left ( mod b ight )) 在 (left [ 0, frac{b}{d} - 1 ight ])上有唯一解。
之前我是不会证明的，现在会了，感谢我Daddy的大力相助。在这里就截一下图（公式写起来好麻烦呀……）
这两条性质让我们知道在求解模意义下的问题时（尤其是在卷积和反演中需要反复变化枚举对象时），可以转化为枚举模后的结果。例如(nx equiv k left ( mod m ight ))，(k in left [ 0, m - 1 ight ])。则当(x in left [ 0, q ight]) 时，(nx mod m = k) 一共出现了(frac{q}{frac{m}{d}}) 次。