整除

　　若\(a\)是\(b\)的因数，或\(b\)是\(a\)的倍数，则\(a\)整除\(b\)，记作\(a\mid b\)。

　　关于整除，有以下几点：

　　1、若\(a\mid b\)，\(b\mid c\)，则\(a\mid c\)。

　　2、若\(a\mid b\)，\(a\mid c\)，则\(a\mid b+c\)。

　　3、若\(a\mid b\)，对于任意的\(k \in \Z\)，都有\(a\mid kb\)。

同余

　　给定整数\(a\)，\(b\)和模数\(p\)，若\(a \bmod p = b \bmod p\)，则称\(a\)和\(b\)在模\(p\)意义下同余，简写成\(a\equiv b \pmod p\)。

　　同余有以下性质：

　　1、\((a \bmod p) \plusmn (b \bmod p) = (a \plusmn b) \bmod p\)

　　2、\((a \bmod p) \times (b \bmod p) = (a \times b) \bmod p\)

　　3、\(\frac{a \bmod p}{b \bmod p} = \frac{a}{b} \bmod p\)（如果你直接算的话，数学老师会揍你，正确姿势放后面）

　　4、\(ax \equiv bx \pmod p \Leftrightarrow a \equiv b \pmod { \frac{ p }{ \gcd(x,p) } }\)

　　\(Proof\)：

裴蜀定理

　　先定义线性组合：形如\(ax+by\)的式子，其中\(a,b,x,y\in \Z\)。

　　裴蜀定理就是：对于任意\(a\)、\(b\)不全为零，则存在\(x\)和\(y\)满足\(ax+by=gcd(a,b)\)。

　　\(Proof\)：

　　这一定理十分常用。

辗转相除法 && 扩展欧几里得算法（Ex-GCD）

　　推论：\(\gcd(a,b)=\gcd(b, a \bmod b)\)。

　　\(Proof\)：

　　同时，这个跟\(Ex-GCD\)的推导大同小异：为了求解\(ax+by=\gcd(a,b)\)方程，利用递归求解，即新的\(x'=y,y'=x-\lfloor \frac{a}{b} \rfloor y\)，当\(b=0\)时是边界，显然\(x=1,y=0\)，此时满足\(ax+by=\gcd(a,b)=a\)。

　　类似的，也可以得到：

　　推论\(1\):\(\forall a,b\in \Z : \gcd(a,b)=\gcd(a-b,b)\)；

　　推论\(2\):\(\forall a,b为偶数:\gcd(a,b)=2 \times \gcd(a/2,b/2)\)；

　　推论\(3\):\(\forall a为偶数,b为奇数:\gcd(a,b)=\gcd(a/2,b)\)。以上式子可以进一步推广成：若\(a=2^i \times a'\)，\(b=2^j \times b'\)，则\(\gcd(a,b)=2^{\min(i,j)} \times \gcd(a',b')\)。

// 求解gcd(a,b)
ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

　　同时有\(\text{lcm}(a,b)\times \gcd(a,b)=ab\)。\(\text{lcm}\)的求解不难了。

　　考虑二元一次方程\(ax+by=c\)，根据上文，该方程有解当且仅当\(\gcd(a,b)\mid c\)。对于\(ax+by=\gcd(a,b)\)解出来\(x_0\)和\(y_0\)，令\(d=\gcd(a,b)\)，则通解为\(\begin{cases}x=\dfrac cdx_0+\dfrac bdt\\\\y=\dfrac cdy_0-\dfrac adt\end{cases},t\in \Z\)。根据上文不难求出来\(x_0\)和\(y_0\)（任意解）

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b) { ll d = exgcd(b, a%b, y, x); y -= a/b*x; return d; } else { x = 1, y = 0; return a; } // 注意暗含的一波换元
}