数的算法

为了更方便的表示一个数，我们通常要选择一个进制。数\(N\)在\(a\)进制下需要\(\log_a N\)位，在\(b\)进制下需要\(\log_b N\)，二者的比值\(\log_b^a\)是常数。因此我们可以认为，对进制的选择是不影响算法的时间复杂度的。

基本算数

加法

从我们在小学时做的列竖式计算中就可以看出，逐位计算并进位的复杂度是正比于数的位数的。设数的位数为\(n\)，则复杂度是\(O(n)\)。同时，仅仅读入数据就要消耗\(O(n)\)，因此这就是加法的最优复杂度了。

乘法

按照列竖式的方法，乘法的复杂度是\(O(n^2)\)。

我们也可以通过这样的递归方法来完成乘法：

\(x \cdot y=\left\{\begin{array}{ll} 2(x \cdot\lfloor y / 2\rfloor) & \text { if } y \text { is even } \\ x+2(x \cdot\lfloor y / 2\rfloor) & \text { if } y \text { is odd } \end{array}\right.\)

递归次数正比于\(y\)的位数\(n\)，每次完成加法的复杂度也是\(n\)，总的复杂度依然是\(O(n^2)\)。

乘法本质上是多项式乘法，通过快速傅里叶变换是可以优化到\(O(n \log n)\)的。

除法

我们想算出\(x\)除以\(y\)的商\(q\)和余数\(r\)。考虑递归，假设已经算出了\(\lfloor x/2\rfloor\)除以\(y\)的余数\(q'\)和\(r'\)。则有\(\lfloor x/2 \rfloor=q' \cdot y + r'\)。两边同时乘以2，得到\(2\lfloor x/2 \rfloor=2q' \cdot y + 2r'\)。如果\(x\)是偶数，那么有\(x=2q' \cdot y + 2r'\)，否则有\(x = 2q' \cdot y + 2r'+1\)。注意如果\(2r'\)或\(2r'+1\)超出了\(y\)，要减一个\(y\)。这样就推出了\(q,r\)。

递归的次数为\(n\)，减\(y\)的复杂度为\(n\)，总复杂度是\(O(n^2)\)。

模运算

对于\(x\)除以\(N\)的商为\(q\)，余数为\(r\)，可以写出\(x = qN+r\)，其中\(r\)被限制在\(\{0,\cdots,N-1\}\)内。如果对于\(y\)也有\(y=q'N+r\)，那么就称\(x\)和\(y\)是同余的。记作

\(x \equiv y \pmod N\)

由此可见\(x-y\)一定是\(N\)的倍数，即\(x-y \equiv 0 \pmod N\)。

如果\(x \equiv x' \pmod N\)，同时\(y \equiv y' \pmod N\)。那么此时有\(x-x' = sN\), \(y-y' = tN\)。那么有\(x+y=(s+t)N+x'+y'\)，所以\(x+y \equiv x'+y' \pmod N\)。而\(xy = (x'+sN)(y'+tN) = x'y'+(tx'+sy'+stN)N\)，所以\(xy \equiv x'y' \pmod N\)。这告诉我们，在模运算中加法和乘法是可以被同余的项代换的。

模运算中由于每个数都被限制在\(\{0,\cdots,N-1\}\)内，因此加法不会超过\(2N-2\)，因此加法以后最多只需要减一次\(N\)就能保证模运算的范围。两数相乘不会超过\((N-1)^2\)，因此需要做一次除法才能保证范围，但我们注意到数字的位数最多只会扩展一倍。

快速幂

在模意义下计算\(x^y\)要用到快速幂算法。核心是：

\(x^{y}=\left\{\begin{array}{ll} \left(x^{2}\right)^{\lfloor y / 2\rfloor} & \text { if } y \text { is even } \\ x \cdot\left(x^{2}\right)^{\lfloor y / 2\rfloor} & \text { if } y \text { is odd } \end{array}\right.\)

递归的次数是\(n\)，每次乘法用去\(n^2\)，复杂度为\(O(n^3)\).

欧几里得算法(GCD)

对于\(x \geq y\)，有\(gcd(x,y)=gcd( x\mod y,y)\)。一直这样递归下去，直到\(x\)成为\(y\)的倍数为止，我们就求出了最大公约数。这称为求解最大公约数的辗转相除法。要证明这个关系，只需证明辗转相减法\(gcd(x,y)=gcd(x-y,y)\)，因为模运算只是减法运算的一种“捷径”。

设\(x,y\)的公约数一定是\(x-y\)的约数。可以设这个公约数为\(k\)，那么有\(x = s \cdot k\)，\(y = t \cdot k\)。于是\(x-y = (s-t) \cdot k\)。因此\(x,y\)的任意一个公约数一定也是\(x-y,y\)的一个公约数。所以一定有\(gcd(x,y) \leq gcd(x-y,y)\)。反之同理，\(x-y,y\)的任意一个公约数一定也是\(x,y\)的一个公约数，所以又有\(gcd(x-y,y) \leq gcd(x,y)\)。联立即得\(gcd(x,y)=gcd(x-y,y)\)。于是辗转相除法也得到了证明。

为了分析辗转相除法的复杂度，我们来估计一下\(x \mod y\)的大小。如果\(y \leq x/2\)，那么\(x \mod y < y \leq x/2\)；如果\(y>x/2\)，那么\(x \mod y = x-y < x/2\)。因此我们每一次至少把一个数缩小了一半，递归的次数是\(O(n)\)的。而模运算的计算复杂度就是除法的复杂度\(O(n^2)\)，因此总的复杂度是\(O(n^3)\)。

扩展欧几里得算法(EXGCD)

对于方程\(ax+by=d\)，左边可以提取出\(a,b\)的最大公约数，因此\(d\)一定是\(gcd(a,b)\)的倍数。换句话说，\(ax+by\)构成的集合一定是量子化的，\(gcd(a,b)\)是最小的单位。

而\(ax+by=gcd(a,b)\)一定是有解的。由欧几里得算法得，\(gcd(a,b)=gcd(b,a \mod b)\)。我们有新的方程\(bx'+(a\mod b)y'=gcd(b,a \mod b)\)。联立可得\(ax+by=bx'+(a\mod b)y'\)。注意到\(a \mod b = a-b\lfloor a/b \rfloor\)。因此有\(ax+by=ay'+b(x'-\lfloor a/b \rfloor y')\)。假设我们已经递归地解得了\(x',y'\)，就可知\(x=y',y=x'-\lfloor a/b\rfloor y'\)是一组可行的解。而由于\(gcd(a,b)\)递归的尽头\(b=0\)，此时\(x\)一定有解，因此返回去最初的\(x,y\)一定有解。