湖面

Bezout 定理

发表于 2022-03-26

简单起见，我们把两个整数 $a$，$b$ 的最大公因数记为 $(a,b)$.

Euclidean algorithm

Theorem 1 若存在整数 $k$ 使得 $a=r+bk$，则 $(a,b)=(b,r)$.

Proof. 由 $r=a-bk$ 得：$a$ 和 $b$ 的公因数都是 $r$ 的因数，也就是 $b$ 和 $r$ 的公因数。所以 $(a,b) \leq (b,r)$. 由 $a=r+bk$ 同理可得 $(b,r) \leq (a,b)$. 因此，$(a,b)=(b,r)$. 证毕。

据此我们可以构造一个数列 $r$，令 $r_{1}=a, r_{2}=b$，并且

\[ r_{i}=r_{i-2} \bmod r_{i-1},\;\;\; 0\leq r_{i} < |r_{i-1}|. \]

不失一般性，我们假设 $a \geq b \geq 0$，那么 $r$ 是单调递减的。所以数列最后一定会出现 $0$，但是 $0$ 不能作为除数，所以我们规定数列在 $0$ 截止，且 $r_{n+1}=0$（也即 $0$ 的前一个数是数列末尾）。

现在要证明

\[ (r_{1}, r_{2})=(r_{2}, r_{3})=\cdots=(r_{n},r_{n+1})=r_{n}. \]

由数列的定义得

\[ r_{i-2}=r_{i}+r_{i-1}q_{i-1}. \]

其中 $q_{i-1}$ 为带余除法 $r_{i-2}/r_{i-1}$ 得到的商。应用上面提到的定理得 $(r_{i-1}, r_{i})=(r_{i-2}, r_{i-1})$. 若 $i=n+1$，则我们可以一路递推至 $i=2$ 的情况，也即 $(a,b)$. 由于 $r_{n+1}=0$，任何数都是零的因数，所以 $(r_{n},r_{n+1})=r_{n}$. 证毕。

这也为我们提供了一种计算最大公因数的高效算法。

Bézout's Identity

Theorem 2 对于任意非零整数 $a$,$b$，存在整数 $x$ 和 $y$ 使得

\[ (a,b)=ax+by. \]

特别地，当 $a$ 与 $b$ 互质时，存在整数 $x$ 和 $y$ 使得 $ax+by=1$

Proof. 使用数学归纳法证明。

下面证明

\[ \forall i \leq n,\,\exists x,y \in \mathbb{Z},\,(r_{i}, r_{i+1})=r_{i}x+r_{i+1}y. \]

初始条件：由 $r_{n+1}=0$ 有

\[ (r_{n}, r_{n+1})=r_{n} \cdot 1 + r_{n+1} \cdot 0. \]

即 $x=1,\ y=0$（$y$ 是不是只能为 $0$？）

递推：假设已存在 $x,y \in \mathbb{Z}$ 使得 $(r_{i}, r_{i+1})=r_{i}x+r_{i+1}y$，现在来证存在 $x',y' \in \mathbb{Z}$ 使得 $(r_{i-1}, r_{i})=r_{i-1}x'+r_{i}y'$.

由数列的定义得

\[ r_{i-1}=r_{i+1}+r_{i}q_{i}. \]

也即

\[ r_{i+1}=r_{i-1}-r_{i}q_{i}. \]

代入递推假设得

\[ \begin{align*} (r_{i}, r_{i+1})&=r_{i}x+r_{i+1}y\\ &=r_{i}x+(r_{i-1}-r_{i}q_{i})y\\ &=r_{i-1}y+r_{i}(x-q_{i}y). \end{align*} \]

又由定理 1 得 $(r_{i}, r_{i+1})=(r_{i-1}, r_{i})$（上面已经证明），所以

\[ (r_{i-1}, r_{i})=r_{i-1}y+r_{i}(x-q_{i}y). \]

且 $y$ 和 $x-q_{i}y$ 都为整数，所以 $x'=y, y'=x-q_{i}y$. 递推证明完成。

结论：当 $i=1$ 时我们得到存在整数 $x,y$ 使得 $(r_{1}, r_{2})=r_{1}x+r_{2}y$ 即 $(a,b)=ax+by$. 证毕。

利用上面的递推过程我们得到了 extended Euclidean algorithm. 它可以计算出 $(a,b)=ax+by$ 的一组整数解。

def exgcd(a, b):
    if b == 0:
        return (1, 0)
    else:
        x, y = exgcd(b, a % b)
        return (y, x-(a//b)*y)


x, y = exgcd(10319, 2312)
print('x =', x, ', y =', y, ', gcd =', a*x+b*y)

Number theory notes

发表于 2022-03-10

Euclidean

Modular arithmetic is congruence, meaning that it is an equivalence relation that is compatible with the operations of addition, subtraction, and multiplication.

\[ \left. \begin{array}{ll} a\equiv b \pmod {n}\\ c\equiv d \pmod {n} \end{array} \right\} \implies a-c \equiv b-d \pmod {n} \]

The Euclidean algorithm just flows out:

\[ \left. \begin{array}{ll} a \equiv 0 \pmod {d}\\ b \equiv 0 \pmod {d} \end{array} \right\} \implies a-kb \equiv 0 \pmod {d} \]

For all $d \in \mathbb{N}^+$, $k \in \mathbb{Z}$, if $d \mid a$ ($d$ is a divisor of $a$), $d \mid b$ ($d$ is a divisor of $b$) and $a \geq b$ then $d \mid a-kb$. Thus we see that $gcd(a,b)=gcd(b, a \bmod b)$.

To describe and proof the algorithm, we can define an array $r$ such that $r_0=a$ and $r_1=b$, while

\[ r_{j}=r_{j-2} \bmod r_{j-1} \]

It basically means

\[ r_{j-2} = r_{j-1}q_{j-1} + r_{j} \]

where $q_{j-1}= [r_{j-2} / r_{j-1}]$ stands for quotient. When hit $r_{n-1} \bmod r_n = 0$, we stop. Thus $r_{n+1}=0$.

Therefore

\[ \begin{gather*} gcd(r_j, r_{j+1})=gcd(r_{j+1}, r_{j+2})\\ r_n= gcd(r_n, 0) = \cdots = gcd(r_0, r_1) \end{gather*} \]

Let $g=gcd(a,b)$, notice that

\[ \begin{align*} g=gcd(r_n,0) &= 1\times r_n + 0\times r_{n+1}=r_n\\ &=r_{n-2}-q_{n-1}r_{n-1}\\ &=r_{n-2}-q_{n-1}(r_{n-3}-r_{n-2}q_{n-2})\\ &=q_{n-1}r_{n-3}+(1+q_{n-2}q_{n-1})r_{n-2}\\ &=\cdots \end{align*} \]

We may wonder if there exists a linear combination such that $g=ax+by$. In fact, this is what Bezout's theorem says.

Proof by induction.

Base case:

\[ g= 1\times r_n + 0\times r_{n+1} \]

Induction step:

Given that $r_{j+1}=r_{j-1}-r_{j}q_{j}$

\[ \begin{align*} g&=r_{j}x_{j}+r_{j+1}y_{j}\\ &=r_{j}x_{j}+(r_{j-1}-r_{j}q_{j})y_{j}\\ &=r_{j-1}y_{j}+r_{j}(x_{j}-q_{j}y_{j}) \end{align*} \]

So $x_{j-1}=y_{j}, y_{j-1}=x_j-q_jy_j$.

Finally,

\[ g=r_0x_0+r_1y_0=ax_0+by_0 \]

This also provides us an algorithm to produce a linear combination.

def exgcd(a, b):
    if b == 0:
        return (1, 0)
    else:
        x, y = exgcd(b, a % b)
        return (y, x-(a//b)*y)


x, y = exgcd(10319, 2312)
print('x =', x, ', y =', y, ', gcd =', a*x+b*y)

References:

The Euclidean Algorithm

Linear Congruences

Suppose you want to solve

\[ ax \equiv c \pmod b \]

and you need to find the minimum integer $x$.

First we can translate it to a normal equation.

\[ ax \equiv c \pmod b \iff ax - c = by \]

Euler's Totient Theorem

发表于 2022-02-20

本篇为交互式 Jupyter Notebook 文档，请在这里查看完整版。

由于叫欧拉定理的定理太多所以就用这个名字了。

在开始讲解之前，首先要问这么一个问题：

$3^{2012} \bmod 17$是多少？

看到取模，我们当然要先找找规律：

1 2	print([3exponent%17 for exponent in range(1, 17)]) print([3exponent%17 for exponent in range(17, 33)])

啊哈！3的幂对17取模，结果是循环的。

所以 $2012 = 125 \cdot 16 + 12$，$3^{2012} \equiv 3^{12} \equiv 4 \pmod {17}$.

我们应该再仔细思考一下，为什么是以16个数为一循环？

因为一个数对17取模，得到的结果只可能在 $[0, 16]$ 这个区间上。而如果一个结果是0，那么其他结果全是0，所以只能在 $[1, 16]$ 上。

那无论底数是什么，都是16个数一循环吗？一定会形成循环吗？

首先来看后面这个问题，答案是会。因为一定会有重复，有重复就会出现循环。

\[ 3^{x} \equiv 3^{y} \pmod {17} \iff 3^{x+1} \equiv 3^{y+1} \pmod {17} \]

对于前一个问题，鉴于有重复就会出现循环，一个循环里面不可能有重复。总共只有16个数，根据鸽巢原理，循环的长度一定小于等于16. 问题也等价于：$[1, 16]$ 中的每一个数都会出现吗？

1	print([2**exponent%17 for exponent in range(1, 17)])

看来并不是。那么接下来怎么办呢？

我们不如换一种思路，看看有没有哪个数是一定会出现的。

1 2	for base in range(0, 17): print(base, [base**exponent%17 for exponent in range(1, 17)])

令人惊奇的是，每个数的第16次方对17取余，结果都是1. 也即

\[ a^{16} \equiv 1 \pmod {17} \]

联想到上面我们证明循环等价于重复的公式：

\[ a^{16} \equiv 1 \pmod {17} \iff a^{16+1} \equiv a \pmod {17} \]

我们如果可以证明上式右边成立，我们就能证明无论如何第1到第16个数都会形成循环了。

作为严谨证明的大纲，先演示对于一个特殊情况：$a=3$，模数为 7 的证明。

我们先看一个引理：如果我们有正整数 $p$ 并且它不被另一个正整数 $a$ 整除，我们可以写下这样的数列

\[ a, 2a, 3a, \cdots , (p-1)a \]

我们对这数列的每一项都对 $p$ 取余，就能得到一个从 $1$ 到 $p-1$ 的全排列。也就是说，每个数都会出现一次。

a = 3
p = 7
print([a*i for i in range(1, p)])
print(perm := [a*i%p for i in range(1, p)])
print(set(perm))

在这之后，我们会把这两个数列分别乘起来。由于前者只是后者的 $a$ 倍，所以它们模 $p$ 同余。

\[ a \times 2a \times 3a \times \cdots \times (p-1)a \equiv 1 \times 2 \times 3 \times \cdots \times (p-1) \pmod p \]

化简得到

\[ a^{p-1}(p-1)! \equiv (p-1)! \pmod p \]

最后，我们会把两边的 $(p-1)!$ “消去”（我知道不能这么直接消，bear with me!）得到

\[ a^{p-1} \equiv 1 \pmod p \]

lhs = 1
for i in range(1, p):
    lhs *= a*i
rhs = 1
for i in range(1, p):
    rhs *= i
print(lhs, '===', rhs, '(mod ' + str(p) + ') is', lhs%7 == rhs%7)
print('Canceling out (p-1)! gives us:')
print(lhs//rhs, '=== 1 (mod ' + str(p) + ') is', (lhs/rhs)%7 == 1)

要完成这个证明，有两个地方需要我们详细说明：

引理：如果我们有正整数 $p$ 并且它不被另一个正整数 $a$ 整除，$i$ 为正整数且 $i \leq p-1$ 时，$\{ia\bmod p\} = \{i\}$
同余式两边何时能同时消去一个数

我们先看第二个：同余式除法，因为第一个依赖第二个证明。

上面我们已经用了同余式两边同时乘上同余的数，同余式仍然成立的性质。除此之外对于加减法也有效。但是对于除法，就没那么简单了。

首先把同余式写成等式。

\[ ac \equiv bc \pmod m \iff \exists k \in \mathbb{Z}, ac = bc + km \]

右式两边同时除以 $c$ 得

\[ a = b + \frac{km}{c} \]

如果 $c \nmid m$ 那么我们还需要换掉整数 $k$ 以使模数为一个整数。

\[ \begin{aligned} k' &= \frac{k \cdot gcd(m, c)}{c} \\ a &= \frac{k'm}{gcd(m, c)} \end{aligned} \]

最后得到

\[ ac \equiv bc \pmod m \iff a \equiv b \ \left(\bmod \frac{m}{gcd(m, c)} \right) \]

如果我们希望前后模数相等，当且仅当 $gcd(m, c) = 1$ 也即 $m$ 与 $c$ 互质才成立。

回到刚才的这个式子

\[ a^{p-1}(p-1)! \equiv (p-1)! \pmod p \]

要让两边消掉 $(p-1)!$ 又不改变模数，有且仅有 $(p-1)!$ 与 $p$ 互质，这等价于 $p$ 为一个质数。7 和 17 都满足这个要求。

现在再来看那个引理：如果有正整数 $p$ 并且它不被另一个正整数 $a$ 整除，$i$ 为正整数且 $i \leq p-1$ 时，$\{ia\bmod p\} = \{i\}$.

首先，小于 $p$ 的数 $i$ 与 $p$ 互质，而 $a$ 也与 $p$ 互质，所以这两个数乘起来仍然与 $p$ 互质（欧几里得引理）。所以 $ia \bmod p \in [1, p-1]$. 然后要证明这些数互不相等。运用反证法，假设有两个不相等的数 $x,y < i$ 使得

\[ xa \equiv ya \pmod p \]

那么由上面推导的同余式除法得

\[ x \equiv y \pmod p \]

而 $x<i, y<i$ 所以 $x=y$ 与假设矛盾。证毕。

至此，证明全部完成。

由上面的推导，我们得到了费马小定理：

对于质数 $p$ 以及任意正整数 $a$ 满足 $p \nmid a$ 有

\[ a^{p-1} \equiv 1 \pmod p \]

如果你足够细心，你也许会注意到我刚才说第二点的时候并没有提到 $p$ 一定是个素数。这让我们不禁想推广刚才得到的成果。我们先来感性的认识一下，当 $p$ 不是素数时是什么样的。因为 $p$ 是 prime 的意思，所以下面换成合数的情况下我们用 $m$ 来代替。

我们先来看看 $m=10$ 的情形：

def extract_repeat(arr):
    for index, value in enumerate(arr[1:]):
        if arr[0] == value:
            return arr[0:index+1]

m = 10
for a in range (1, m):
    print('a =', a, arr := [a**exponent%m for exponent in range(1, m)], extract_repeat(arr))

注意到，当 $a$ 与 $m$ 有公因数的时候，循环不一定会出现 1. 这是为什么呢？任意整数 $k$，$km+1$ 这时候都肯定跟 $m$ 互质，因此 $a^{x} \neq km+1$.

有没有整数 $a,x$ 使得

\[ a^x \equiv 1 \pmod m \]

呢？要找到这个数，我们就得找到一个数列 $T$，使其满足我们上面的两点要求

对每个数乘以 $a$ 再 $\bmod \ m$ 得到的数列是 $T$ 的全排列
把 $T$ 中的数全乘起来，得到的数与 $m$ 互质（可以从同余式两边消去）

在 $m = p$ 的情况下，我们已经看到了 $T=\{1,2,3,\cdots,p-1\}$. 现在考虑的是 $m$ 不为质数的情况。

先看第一点。需要 $T$ 中的数 $t_i$ 都与 $m$ 互质，$a$ 与 $m$ 互质，以及 $t_ia \bmod m \in T \implies T$ 是比 $m$ 小且与 $m$ 互质的数的集合。

再看第二点，由 $T$ 是与 $m$ 互质的数的集合，$T$ 中的数全乘起来，得到的数与 $m$ 互质，满足条件。

下面开始外层证明。令 $r$ 为 $T$ 中所有数的乘积，即 $r = \prod t_i$. $\phi(m)$ 为 $m$ 对应的数组 $T$ 中的元素个数。

\[ \begin{aligned} at_1 \times at_2 \times \cdots \times at_n &\equiv t_1 \times t_2 \times \cdots \times t_n \pmod m \\ a^{\phi(m)} r &\equiv r \pmod m \\ a^{\phi(m)} &\equiv 1 \pmod m \end{aligned} \]

import math
def phi(m):
    res = []
    for k in range(1, m+1):
        if math.gcd(k, m) == 1:
            res.append(k)
    return res

def prod(arr):
    res = 1
    for t in arr:
        res *= t
    return res
    
a = 3
m = 10
T = phi(m)
r = prod(T)

print(prod([a*t for t in T]), '===', r, '(mod ' + str(m) + ') is', prod([a*t for t in T])%m == r%m)
print(a**len(T)*r, '===', r, '(mod ' + str(m) + ') is', a**len(T)*r%m == r%m)
print(a**len(T) , '=== 1', '(mod ' + str(m) + ') is', a**len(T)%m == 1%m)

这就证明了欧拉定理（数论）：

$m$ 和 $a$ 是互质的正整数，$\phi(m)$ 为小于等于 $n$ 的正整数中与 $n$ 互质的数的数目（欧拉函数），有

\[ a^{\phi(m)} \equiv 1 \pmod m \]

参考资料：

前端入门好文推荐

发表于 2021-12-15

最近一周简单学了下 React 和 JavaScript，把遇到的各种难点整理一下，附上我能找到的好文：

JavaScript

通用

现代 JavaScript 教程（The Modern JavaScript Tutorial）

理解 this 和函数调用

理解箭头函数

箭头函数 - MDN

面向对象

模块

JavaScript Modules: A Beginner’s Guide

函数式编程

Mostly adequate guide to functional programming (in javascript)（中文译版）

CSS

React

官方文档作为入门资料已经很好了。下面是进阶补充，主要是思想介绍：

简析动态规划

发表于 2021-12-04

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划是一种在 OI 中非常常见的算法。如上所述，动态规划的精髓在于子问题，然而并不是所有和子问题相关的算法都是动态规划。要搞清楚动态规划是什么、为什么、怎么用，我们可以从两种方向来认识。

重叠子问题

例题1：

蒜头君很喜欢爬楼梯，这一次，他获得了一个特异功能，每次可以跳跃任意奇数的阶梯。比如他初始在楼底，跨越一个阶梯到达 11 号阶梯，或者跨越 3 个楼梯到达 3 号阶梯。如下图

为了选出一种最轻松的爬楼梯的方式，蒜头君想把所有不同的到达楼顶的方式都尝试一遍。对于一共有 $n$ 个阶梯的楼梯，蒜头君一共有多少种方法从楼底到达楼顶？

最暴力的做法就是递归搜一遍：

typedef long long ll;
ll path(ll n) {
    if (n == 0) {
        return 1;
    } else {
        ll ans = 0;
        for (int i = 1; n - i >= 0; i += 2) {
            ans += path(n - i);
        }
        return ans;
    }
}

时间复杂度 $O(n!)$，但其实这离答案就差一点。

Tips: 你要知道第 $n$ 个阶梯的方案数，你只需要知道到第 $n-1$, $n-3$, $n-5$…… 个阶梯的方案数。

我怎么知道？存下来就行了呗：

typedef long long ll;
ll memory[MAXN] = {0};
ll path(ll n) {
    if (memory[n]) {
        return memory[n];
    }
    if (n == 0) {
        return 1;
    } else {
        ll ans = 0;
        for (int i = 1; n - i >= 0; i += 2) {
            ans += path(n - i);
        }
        memory[n] = ans;
        return ans;
    }
}

这么一来，时间复杂度就变成 $O(n)$ 了。

思路：因为 \[ path_{n} =path_{n-1} +path_{n-3}+...+path_{n-(2k-1)} \] 所以用数组记录每个子问题的解以避免重复计算。

这就是重叠子问题，通过对重叠子问题的记忆，可以极大地优化很暴力的算法。

重叠子问题，在编程层面上常常表现为纯函数。如果你曾经接触过函数式编程（比如使用 React 之类的库或者 Haskell 语言），你可能听说过这个概念。纯函数是一个满足以下条件的函数：

输入参数相同时，输出值相同。
不能有语义上可观察的副作用，比如更改输出值以外变量的内容等。

上文所述 path 函数正好满足这些要求。因此，我们可以放心地根据参数缓存它的返回值。

最优子结构

Leetcode 最小路径和

给定一个包含非负整数的 $m\times n$ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

同样先用递归写

typedef long long ll;
int min_path(int x, int y) {
    if (x == 1 && y == 1) {
        return grid[x][y];
    } else if (x == 1) {
        return min_path(x, y - 1) + grid[x][y];
    } else if (y == 1) {
        return min_path(x - 1, y) + grid[x][y];
    } else {
        return min(min_path(x - 1, y), min_path(x, y - 1)) + grid[x][y];
    }
}

你现在肯定在想：记忆化！开个数组 min_path[x][y] 把遍历到的结果全存下来，如果已经算过直接返回不就行了！

先等一下，我们先想想，这个 min_path 函数在语义上是什么用途呢？是从 $(1,1)$ 前往 $(x,y)$ 的最小距离。那你怎么就肯定 $(x,y)$ 变了以后，你存下来的还是对应的最短距离呢？

换句话说，记忆化的前提是：无论终点是哪一个，到达终点的路径上的点之间走的全部都是最短距离，不存在有需要绕路的情况。

这就是最优子结构。一个解是最优的，那么它在子问题中也必定是最优的。

再看一道题：

P1541 [NOIP2010 提高组] 乌龟棋

简单写个暴力递归

#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 351;
const int MAXM = 121;
int a[MAXN];
int b[MAXM];
bool used[MAXM];
int n, m;
int max_scores(int x) {
    if (x == 1) {
        return a[x];
    } else {
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            if (!used[i]) {
                used[i] = true;
                ans = max(ans, max_scores(x - b[i]) + a[x]);
                used[i] = false;
            }
        }
        return ans;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    memset(used, 0, sizeof(used));
    cout << max_scores(n);
}

这时候，还能记忆化吗？

不行了。因为函数返回的值不但跟终点位置 x 有关，还跟使用爬行卡片情况的数组 used 有关。显然，这个函数不满足上面所说纯函数的两个要求。如果你把 used 也当成参数加进来，那么每次 used 的值都会不同，记忆化没有意义。

这是为什么呢？原因就是现在我们的函数 max_scores(int x) 不具有最优子结构了。当前贪心地把前 x 个格子的分数拿到最大用掉了爬行卡片，后面就会受影响得不到最优的结果。正是因为有了最优子结构，子问题才会重叠。最优子结构是因，重叠子问题是果。

那，这题就不能用动态规划做了？

仔细观察题目：

分成4种不同的类型（$M$ 张卡片中不一定包含所有 4 种类型的卡片，见样例），每种类型的卡片上分别标有 1, 2, 3, 4 四个数字之一。

总共只有四种类型的卡片，而相同数字的卡片没有任何区别。重叠子问题！写一下试试：

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 351;
const int MAXM = 121;
const int MAXB = 41;
int score[MAXN];
int n, m;
int memory[MAXB][MAXB][MAXB][MAXB];
int max_scores(int* use) {
    if (memory[use[0]][use[1]][use[2]][use[3]]) {
        return memory[use[0]][use[1]][use[2]][use[3]];
    }
    if (use[0] == 0 && use[1] == 0 && use[2] == 0 && use[3] == 0) {
        return score[1];
    } else {
        int ans = 0;
        int x = 1;  // start from 1
        for (int i = 0; i < 4; i++) {
            x += use[i] * (i + 1);
        }
        for (int i = 0; i < 4; i++) {
            if (use[i] != 0) {
                use[i]--;
                ans = max(ans, max_scores(use) + score[x]);
                use[i]++;
            }
        }
        memory[use[0]][use[1]][use[2]][use[3]] = ans;
        return ans;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    int b;
    int cnt[4] = {0, 0, 0, 0};
    for (int i = 1; i <= m; i++) {
        cin >> b;
        cnt[--b]++;
    }
    cout << max_scores(cnt);
}

顺利 AC. 我们可以发现，选取递归函数的参数和语义是解决此问题的关键。

虽然这个函数在形式上仍然不满足纯函数的要求，但是这仅仅是为了方便。你完全可以用更加啰嗦的形式，将参数由一个数组指针改成四个整型，把这个函数改造成一个纯函数。

形式不重要

动态规划在狭义上一般都是从最小的子问题开始，一步一步求解更大规模的问题，所以它的实现都是循环，而不是递归。然而，上面讲的全部都是递归，这种方法会被单独称作记忆化搜索。但是我这么做的原因正是想说明一点：形式不重要，重要的是子问题的解之间的依赖关系。

这里引用知乎上的一篇回答：

动态规划的初衷是，

通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，使得最终的目标能变成一个函数在某组自变量下的值：比如在经典题目数字三角形中，将“和”在“横纵坐标”上展开，那么最终的目标就是 $max\{f(n - 1, i)\}$，$i$ 从 $0$ 到 $n-1$.

这种展开需要满足的性质是：首先，展开后，函数值是可以由自变量唯一确定的；其次，函数有一种递推表达式；最后，可以通过某种求值顺序（待求的所有函数值的依赖关系形成一个有向无环图），从显然的初值开始依次求，直到目标值。

至于是用循环解，还是记忆化搜索解，还是用 BFS 或者 DFS 解，都不本质。这个依赖于上文所说的有向无环图的结构。

而求解这个问题，正是遍历这张有向无环图上和答案点直接或间接相连的所有点。

我们可以用最暴力的方法去递归，这就对应着在那个有向无环图中从我们要求解的那个点开始，完全按照有向边走。可以想见，这么走必定会大量重复经过点，这就是它低效的原因。

那我们可以怎么优化呢？记忆化搜索给出的答案是把走过的点的结果存起来，下一次就不往下走了，这样就避免了绝大部分重复经过的情况。

而使用循环的动态规划则是从最底部已知的边界点开始，倒着往上遍历。它并不依赖图之间的有向边遍历，而是按照预设好的路线遍历。这就需要保证遍历到的每个点的依赖都已被遍历。

所以说，能用动态规划求解的问题一定能用记忆化搜索求解。

计算机只会穷举。所有算法都是在充分利用给定的条件，让计算机更优雅地穷举。

安装和配置 Flarum

发表于 2021-12-02

本文采用 Ubuntu 20.04 LTS.

安装 MariaDB、PHP 和 Composer

更新源

1	sudo apt update

首先安装 php（Apache 2 的 php 模块）

sudo apt-get install apache2 mariadb-server php7.4 libapache2-mod-php7.4 php7.4-common php7.4-mbstring php7.4-xmlrpc php7.4-soap php7.4-mysql php7.4-gd php7.4-xml php7.4-curl php7.4-cli php7.4-zip php7.4-tokenizer wget unzip curl git -y

然后全局安装 Composer

1 2	curl -sS https://getcomposer.org/installer \| php sudo mv composer.phar /usr/local/bin/composer

配置数据库

运行

1	sudo mysql_secure_installation

Enter current password for root (enter for none): Just press the Enter
Set root password? [Y/n]: Y
New password: Enter password
Re-enter new password: Repeat password
Remove anonymous users? [Y/n]: Y
Disallow root login remotely? [Y/n]: Y
Remove test database and access to it? [Y/n]: Y
Reload privilege tables now? [Y/n]: Y

sudo mysql -u root -p
create database flarum character set utf8mb4 collate utf8mb4_unicode_ci;
CREATE USER 'flarumuser'@'localhost' IDENTIFIED BY 'new_password_here';
GRANT ALL ON flarum.* TO 'flarumuser'@'localhost' IDENTIFIED BY 'user_password_here' WITH GRANT OPTION;
FLUSH PRIVILEGES;
EXIT;

安装 Flarum 并配置 Apache

创建目录并使当前用户成为所有者。这是为了避免以 root 运行 Composer.

1 2	sudo mkdir -p /var/www/flarum sudo chown -R $USER:$USER /var/www/flarum

安装

1 2	cd /var/www/flarum composer create-project flarum/flarum .

然后，使 Apache 成为该目录的所有者

1	sudo chown -R www-data:www-data /var/www/flarum

添加 Apache 的 VirtualHost

1	sudo vim /etc/apache2/sites-available/flarum.conf

写入以下内容

<VirtualHost *:80>
    ServerAdmin admin@your_domain.com
    DocumentRoot /var/www/flarum/public
    ServerName your-server
    <Directory /var/www/flarum/public>
        Options FollowSymlinks
        AllowOverride All
        Require all granted
    </Directory>
    ErrorLog ${APACHE_LOG_DIR}/your-domain.com_error.log
    CustomLog ${APACHE_LOG_DIR}/your-domain.com_access.log combined
</VirtualHost>

启用新的 VirtualHost 和 URL 重写模块，并通过重启服务来应用更改。

sudo a2ensite flarum
sudo a2enmod rewrite
sudo a2dissite 000-default.conf
sudo systemctl restart apache2

检查是否已打开防火墙。

配置 HTTPS

安装 certbot

1	sudo apt install certbot python3-certbot-apache

确保 flarum.conf 中填入了正确的域名。

允许 SSL 通过防火墙

检查云服务提供商的防火墙已打开 443 端口
检查 ufw 设置 sudo ufw status

申请 SSL 证书

1	sudo certbot --apache

常见 Wrong Answer 原因集锦

发表于 2021-12-01

变量运算过程中溢出

Codeforces #137522685

Diagnostics detected issues [cpp.clang++-diagnose]: p71.cpp:66:40: runtime error: signed integer overflow: 99999 * 100000 cannot be represented in type 'int'

尽管指定运算结果会被赋值/加到一个较大的数据类型（比如 long long），运算过程中仍然会有精度问题。

解决方案：保证所有运算中变量数据类型一致。

`std::cout` 输出浮点数精度问题

std::cout << std::cout.precision(); 默认输出为 6. 即最多输出小数点后 6 位。

解决方案：

std::cout << std::setprecision(int n)
printf("pi = %.5f", 4*atan(1.0));

负数取余取模问题

在数学上模运算一般是根据欧几里得除法（带余除法）定义的：

对于任意整数 $a$, $b$ $(b\neq 0)$ 存在唯一的整数 $q$ 和 $r$ 使得 $0 \leq r < |b|$ 且

\[ a = bq + r \]

则 $r = a \bmod b$.

注意，这里规定了 $r \geq 0$.

对于 $a \geq 0, b > 0$ 的情况，一切正常。

但是如果 $a < 0$ 问题就出现了：

\[ \begin{align*} -5 &= 3 \cdot (-1) + (-2) \\ -5 &= 3 \cdot (-2) + 1 \end{align*} \]

按照上面的定义 $-5 \bmod 3 = 1$，但是在 C++ 中结果是 $-2$.

为什么？这是因为 C++ 的 % 运算符是取余而非取模。

1
2
3

int remainder(int a, int b) {
    return a - (a / b) * b;
}

换句话说，C99 标准要求，a == b * (a / b) + a % b. 也即 q = a / b，r = a % b.

$-5/3 = -1.\dot{6}$，按照 C++ 的标准去掉小数部分即为 $-1$. 这就是问题所在：C++ 中的商取整永远都是朝着 0 取。

再来看几个例子：

\[ \begin{align*} -5 &= (-3) \cdot 1 + (-2)\\ -5 &= (-3) \cdot 2 + 1 \end{align*} \]

而 C++ 中 -5 / -3 = 1 所以 -5 % -3 = -2. 如果商取整朝着负无穷取的话，那么结果的正负号和除数一致。

\[ \begin{align*} 5 &= (-3) \cdot (-1) + 2\\ 5 &= (-3) \cdot (-2) - 1 \end{align*} \]

此时 % 运算符和取模匹配。

据此我们可以归纳得出，C++ 中的 % 运算符结果正负号与被除数一致。当被除数大于等于 0 的情况下，% 运算符和取模结果一致。否则需要在结果上加上除数的绝对值。

int mod(int a, int b) {
    int r = a % b;
    return r < 0 ? r + abs(b) : r;
}

最后来看看 Python:

>>> -5 % 3
1
>>> -5 % -3
-2
>>> 5 % -3
-1

显然 Python 中商取整都是朝着负无穷取。

>>> -5 // 3
-2
>>> -5 // -3
1
>>> 5 // -3
-2

零编程基础自建免费博客指南

发表于 2021-11-29

本文的标题中强调了“零基础”，但是你仍然需要用到一些常见的开发工具。但请放心，上手使用这些工具并不难！这只需要你有足够的耐心，和一定的信息搜索能力。另外，如果能稍微了解一下原理而不是不求甚解拿来就用，那么维护博客对你来说就更不是件难事。

从这里开始

Hexo 使用 Markdown 作为文章的格式，所以你需要了解 Markdown 标记语言并选择一个趁手的 Markdown 编辑器。这方面的选择很多，我个人以前一直在用 Typora，但是最近它开始收费了。所以我推荐你用开源的在线 Markdown 编辑器 Arya. 即时预览的界面用起来几乎把学习成本降到了最低。

原理

为什么 Hexo 的运作不需要服务器呢？其实 Hexo 只干了一件事：把编辑器输出的 Markdown 文档（Microsoft Word 虽然也是这一类文件，但是不被 Hexo 支持）转换成 HTML 5 网页（包括 HTML、CSS、JavaScript）。而这些网页从此就算「独立」了：不需要与生成它的那台机器相连接，它自己就能在任何能打开它的浏览器上工作，也不需要在任何服务器上运行代码。所以，我们只需要给这些网页找一个「网盘」（前提是得支持 HTTP 连接），就能通过访问这个网盘打开网页了。

而是谁运行 Hexo，编译输出网页呢？我们这里用的是 Cloudflare 免费提供的自动构建服务器。你也可以在你自己的计算机上做这个事情，具体操作请看 Hexo 官方文档。

注册

你需要在两个地方注册账号：

GitHub：与 Git 深度集成，用于存放博客源代码库。
Cloudflare：用于托管编译出的博客。

这两者都只需要邮箱注册。另外尽管这次使用 Cloudflare 提供的托管服务，GitHub 同样也有类似的 GitHub Pages，而它提供的域名其中一部分将是你的用户名。加上用户名注册后不可更改，建议你选一个你喜欢的、好记且好输入的用户名。

配置

注册完成之后请打开我预先准备好的模板。然后点击 Use this template，填入你的存储库名称（如 blog-source）然后直接点击 Create repository from template.

登入 Cloudflare 控制台，点击右边栏的 Pages，然后点击 Create a project. 再下一个页面中点击 Connect GitHub，授权访问你刚刚创建的存储库（或者所有存储库）。再次回到创建 project 的页面，选中你的存储库并下一步。

在 Project name 中填入你博客的名字（将成为你博客域名中的一部分，所以建议你选一个你喜欢的、好记且好输入的名字）
在 Build command 中填入 npm run build
在 Build output directory 中填入 public

其他都保持默认，点击 Save and deploy.

等2到3分钟后，访问 [名字].pages.dev，看看博客是不是已经出现了？

自定义

Hexo 的配置是用 YAML 格式写的。所以简单了解一下它的格式会极大地帮助你修改配置以及减少出错概率。但是目前来说，你只需要记住以下几点：

数据之间的层级关系是通过缩进来体现的，所以你必须严格遵守缩进，且只能使用空格。
单个配置值使用冒号结构表示 key: value，注意冒号后有一个空格。
# 开头的为注释

准备好后打开你刚刚在 GitHub 上创建的博客存储库，点开主目录下的 _config.yml 文件，然后在文件内容上方的右侧找到修改按钮（图标为一支笔）点开。

这时你就在修改你的 Hexo 配置文件了，这个配置文件的详细说明文档在此处。但如果你没有额外要求，只用改以下几个部分：

title 网站标题
subtitle 网站副标题（可选）
author 你的名字
url 填入[名字].pages.dev

填好以后直接点击 Commit changes 提交更改。

可选：然后重复相同的步骤，修改 _config.next.yml 文件，这是主题的配置文件。详细文档在此处。你可以参考文档挑选一个你喜欢的主题。在大多数情况下，你不需要修改其它的配置。

修改完以后过2到3分钟再次访问你的博客，看看有什么变化？

写作

你的文章存放在 source/_posts 目录中，修改文章的方式和修改配置基本相同，但是有一点需要注意：每个文章开头都会有这一段：

---
title: Hello World
date: 2021-01-01 00:00:00 +08:00
tags: [标签1,标签2,标签3]
mathjax: true
---

这个叫做 YAML front matter，其实就是在 Markdown 文件头部加了一段 YAML 格式的配置/说明。你需要注意的是如果文章中有数学公式需要加上一行 mathjax: true。

小技巧：Hexo 会使用每篇文章的文件名作为它的 URL，但是中文出现在 URL 中很不美观，你可以把文章英文名作为 Markdown 文件的名字（全部小写，空格换成短横线，如 hello-world），然后在 title: 你好世界 这里写这篇文章的中文名。实际页面中文章的名字全部取决于这个 title 的值。

如果要新建一篇文章，你可以导航到 source/_posts 目录，然后点击 Add file，选择创建新文件（直接在网页编辑）或是从本地上传 Markdown 文件。

每次博客存储库有更改，在2到3分钟后网站即会更新。

算法竞赛常用模板

发表于 2021-11-26

基础算法

快速幂

typedef long long ll;
ll quick_pow(ll base, ll exp) {
    int result = 1;
    while (exp) {
        if (exp & 1) {
            result *= base;
        }
        exp >>= 1;
        base *= base;
    }
    return result;
}

二分查找

给定长度为n的数组（$n\geq 1$）

问题1：找到值为value的元素的下标

int BinarySearch(int array[], int n, int value) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        // 注意防止溢出
        int middle = left + ((right - left) >> 1);
        if (array[middle] > value) {
            right = middle - 1;
        } else if (array[middle] < value) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}

问题2：找到第一个值为value的元素的下标

这时候遇到相等也不能直接返回，只能排除掉右侧的所有数。

数组的长度为 1 或 2 时，middle为 0. 若array[0]为要找的数，则right将被赋值为 -1，循环结束，left为答案。数组长度为 2 且array[1]为要找的数时，left将被赋值为 1，回到数组长度为 1 的情况。

因此最后再判断一下left是否为要找的数，如果是则返回，否则答案不存在。

int BinarySearch(int array[], int n, int value) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int middle = left + ((right - left) >> 1);

        if (array[middle] >= value) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }

    if (left < n && array[left] == value) {
        return left;
    }
    return -1;
}

问题3：找到最后一个值为value的元素的下标

这就是问题2的倒序版本。改动两个地方即可

if (array[middle] >= value) 中的等号去掉；
if (right >= 0 && array[right] == value) {return right;}

问题4：找到第一个大于等于value的下标

在问题2中，我们的策略是让left刚好为第一个大于等于value的数的下标，而让right刚好为第一个小于value的数的下标。因此只需要去掉最后判断答案存在的array[left] == value条件即可。

问题5：找到最后一个小于等于value的下标

与问题4同理，去掉问题3中最后判断答案存在的array[right] == value条件。

数论

欧拉筛

bool is_prime[MAXN];
int prime[MAXN];
int sieve(int n) {
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[1] = 0;
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
    return cnt;
}

辗转相除法求最大公因数（Greatest Common Divisor）

最大公因数的算法是辗转相除法，基于一个原理：如果$a>b$则$gcd(a,b)=gcd(b,a-b)$.

如果$a-b>b$，那么就继续相减到$a-b<b$为止，所以直接$gcd(a,b)=gcd(b,a\bmod b)$.

代码：

int gcd(int a, int b) {
    int tmp;
    while (b != 0) {
        tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

最小公倍数（Least Common Multiple）

两个数的最大公因数（Greatest Common Divisor）就是它们质因数的交集的乘积

考虑最小公倍数的性质。最小公倍数必须被$a$或$b$整除，也就是说最小公倍数必须同时包含这两数的所有质因数，所以是它们质因数的并集的乘积。怎样得到这个乘积？$a\times b$，然后容斥除掉共同的质因数$gcd(a,b)$就好了。 \[ lcm(a,b)=\dfrac{a\times b}{gcd(a,b)} \] 实际编程中一般先除后乘，防止溢出。

代码：

1
2
3

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

裴蜀定理

裴蜀定理，又称贝祖定理（Bézout's lemma）。是一个关于最大公约数的定理。

其内容是：

设 $a,b$ 是不全为零的整数，则存在整数 $x,y$, 使得 $ax+by=\gcd(a,b)$.

证明：

1
2
3

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

在函数返回之前，存在$b=0$. 这时显然有$x=1,y=0$使得 \[ a\cdot 1+0\cdot 0=gcd(a,0) \] 0 和任何数的最大公约数都等于原数。

当$b>0$时，有$gcd(a,b)=gcd(b,a\bmod b)$. 假设存在$x,y$使得 \[ bx+(a\bmod b)y=gcd(b,a\bmod b) \] 且 \[ a\bmod b=a-b\cdot \left\lfloor \dfrac{a}{b} \right\rfloor \] 所以 \[ \begin{aligned} bx+(a\bmod b)y&=bx+\left(a-b\cdot \left\lfloor \dfrac{a}{b} \right\rfloor\right)y\\ &=ay-b\left(x-\left\lfloor \dfrac{a}{b} \right\rfloor y\right ) \end{aligned} \] 令$x'=y,\ y'=x-\left\lfloor \dfrac{a}{b} \right\rfloor y$，可得 \[ ax'+by'=gcd(a,b) \] 用归纳法即可得证。

参考：https://www.cnblogs.com/fusiwei/p/11775503.html

扩展欧几里得

为什么叫它扩展欧几里得呢？因为它就是在欧几里得算法（辗转相除法）求得$gcd(a,b)$的基础上，像上面裴蜀定理的证明那样倒着回溯找了一组$x,y$满足 \[ ax+by=gcd(a,b) \] 具体代码请看下面的线性同余方程。

线性同余方程（线性丢番图方程）

形如$ax\equiv c\pmod b$的方程被称为线性同余方程 (Congruence Equation)。

求解方法

根据以下两个定理，我们可以求出同余方程 $ax \equiv c \pmod b$ 的解。

定理 1：方程 $ax+by=c$ 与方程 $ax \equiv c \pmod b$ 是等价的，有整数解的充要条件为 $\gcd(a,b) \mid c$。

根据定理 1，方程 $ax+by=c$，我们可以先用扩展欧几里得算法求出一组 $x_0,y_0$，也就是 $ax_0+by_0=\gcd(a,b)$，然后两边同时除以 $\gcd(a,b)$，再乘 $c$。然后就得到了方程 $a\dfrac{c}{\gcd(a,b)}x_0+b\dfrac{c}{\gcd(a,b)}y_0=c$，然后我们就找到了方程的一个解。

定理 2：若 $\gcd(a,b)=1$，且 $x_0$、$y_0$ 为方程 $ax+by=c$ 的一组解，则该方程的任意解可表示为：$x=x_0+bt$，$y=y_0-at$, 且对任意整数 $t$ 都成立。

根据定理 2，可以求出方程的所有解。但在实际问题中，我们往往被要求求出一个最小整数解，也就是一个特解 $x=(x \bmod t+t) \bmod t$，其中 $t=\dfrac{b}{\gcd(a,b)}$。

int ex_gcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int d = ex_gcd(b, a % b, x, y);
  int temp = x;
  x = y;
  y = temp - a / b * y;
  return d;
}
bool liEu(int a, int b, int c, int& x, int& y) {
  int d = ex_gcd(a, b, x, y);
  if (c % d != 0) return 0;
  int k = c / d;
  x *= k;
  y *= k;
  return 1;
}

常用 STL

比较两个 string 是否相等

std::string::compare

string (1)	`int compare (const string& str) const noexcept;`
substrings (2)	`int compare (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen = npos) const;`
c-string (3)	`int compare (const char* s) const; int compare (size_t pos, size_t len, const char* s) const;`
buffer (4)	`int compare (size_t pos, size_t len, const char* s, size_t n) const;`

返回值

value	relation between compared string and comparing string
`0`	They compare equal
`<0`	Either the value of the first character that does not match is lower in the compared string, or all compared characters match but the compared string is shorter.
`>0`	Either the value of the first character that does not match is greater in the compared string, or all compared characters match but the compared string is longer.

从容器中删除指定的元素

从字符串中删除某些字符

#include <algorithm>
void removeCharsFromString( string &str, char* charsToRemove ) {
   for ( unsigned int i = 0; i < strlen(charsToRemove); ++i ) {
      str.erase(remove(str.begin(), str.end(), charsToRemove[i]), str.end());
   }
}

std::remove

1 2	template <class ForwardIterator, class T> ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);

解读高等数学中那些难懂的符号

发表于 2021-11-13

微分符号和积分符号

准备工作：

了解极限的定义以及相关的无穷小等概念。
了解导数是什么。
了解极限运算法则和求导法则。
理解“微分是函数的线性近似”

很多人都说《高等数学》难学，一部分缘于求极限、求导和积分是全新的、之前没有接触过的运算，要掌握和熟练运用需要不少苦功夫；另一部分就要归结于编书者用“惯例”来搪塞各种解释的高傲态度。

第二章中，先介绍导数，再介绍微分。这导致前面突然就冒出个$\dfrac{\mathrm{d}}{\mathrm{d}x}$求导符号。然而介绍微分的时候又草草带过。基本上，书中是这样定义微分运算的：对函数$y=f(x)$，如果$x_0$和$x_0+\Delta x$在定义域内且 \[ \Delta y=f'\left( x\right) \Delta x+o\left( \Delta x\right) \] 那么记作 \[ \mathrm{d}y=A\Delta x. \] 并且通常把自变量$x$的增量$\Delta x$称为自变量的微分，记作$\mathrm{d}x$，即$\mathrm{d}x=\Delta x$. 所以函数$y=f(x)$的微分记作 \[ \mathrm{d}y=f'(x)\mathrm{d}x. \] 嗯？这就结束了？

所以微分是什么呢？难道跟我们学的加减乘除一样，就是一个运算符号？

是，也不完全是。

回想书中前面的内容，我们一直把求导符号$\dfrac{\mathrm{d}}{\mathrm{d}x}$称为“算子”。其实这个概念在第一章第一节早有介绍，只不过大部分人都会忽略：

映射又称为算子。根据集合$X$、$Y$的不同情形，在不同的数学分支中，映射又有不同的惯用名称。例如，从非空集$X$到数集$Y$的映射又称为$X$上的泛函，从非空集$X$到它自身的映射又称为$X$上的变换，从实数集（或其子集）$X$到实数集$Y$的映射通常定义为$X$上的函数。

那么求导是怎样的一种映射？显然是一个原函数映射成一个导函数。那微分呢？ \[ \begin{align} y&=x^2\\ \mathrm{d}y&=2x\mathrm{d}x \end{align} \] 是函数映射成函数吗？看着不像啊！这怎么又有$x$又有$\mathrm{d}x$，难道是二元函数？

你可以这么理解，但是我认为一个（在数学上是等价的）更好的理解是：对于每一个$x$，都有一个对应的函数$g(\mathrm{d}x)=2x\mathrm{d}x$. 这个函数是$y$在$x$附近的线性近似。微分就是把一个函数映射到这样一个实数到函数的映射（若嫌麻烦也可以理解成二元函数）上面。

到这里，有必要解释一下为啥书里面不先介绍微分了。这其实是个历史遗留问题。微分的符号$\mathrm{d}$最早是莱布尼茨发明的（顺便一提，积分符号也是他发明的），他把$\Delta x$和$\Delta y$当成是有限的增量，对应的$\mathrm{d}x$和$\mathrm{d}y$就是无穷小增量。然而麻烦的是，莱布尼茨对于无穷小和微分的定义是很不精确的（莱布尼茨发明微积分的时候还没有极限的严格定义，具体可以参考这里的回答），所以我们现在学习的并不是他的理论。然而我们要学他的符号，因为这已经是“惯例”了。我们学习的是 \[ \dfrac{\mathrm{d}}{\mathrm{d}x}y=\lim _{\Delta x\to 0}{\frac {\Delta y}{\Delta x}} \] 其中$\dfrac{\mathrm{d}}{\mathrm{d}x}$就是一个写得比较奇怪的记号。那么你可能会问：先讲微分，不就没这么多破事了吗？不好意思，不行。因为我们现在采用的是柯西给出的微积分定义（极限的严格定义也是柯西给出的）。他是用导数定义微分的： \[ \mathrm{d}y=f'(x)\mathrm{d}x. \] 这下死循环了。所以编书者没办法，就这么将就学吧。

有人会问：不是说牛顿和莱布尼茨同时发明了微积分吗？牛顿的符号为啥没流传下来呢？其实现在也在用，就是$\dot {y}$，表示$y$的一阶导数，二阶就是加两个点，三阶就是加三个点，以此类推。但是这样写并没有显式地指明自变量是什么，容易造成误解。

莱布尼茨符号流行的另外一个原因是它能辅助记忆用于微分和积分的公式。比如链式法则：假设函数$g$在$x$处可微，$y = f(u)$在$u = g(x)$处可微。那么复合函数$y = f(g(x))$在$x$处是可微的，其导数用莱布尼茨符号表示为： \[ \dfrac{\mathrm{d}y}{\mathrm{d}x}=\dfrac{\mathrm{d}y}{\mathrm{d}u}\cdot \dfrac{\mathrm{d}u}{\mathrm{d}x} \] 把$\mathrm{d}u$消……等等！谁告诉你能这么消的？ \[ \dfrac{\mathrm{d}y}{\mathrm{d}x}=\lim _{\Delta u\to 0}{\frac {\Delta y}{\Delta u}} \cdot \lim _{\Delta x\to 0}{\frac {\Delta u}{\Delta x}} \] 用极限形式写出来。显然，这两个极限的变量都不一样，不可以消去。

如果要证明链式法则，我们可以利用微分的概念。 \[ \begin{align} \Delta y&=f'(u)\Delta u+o(\Delta u)\\ &=f'(u)\left[g'(x)\Delta x+o(\Delta x)\right]+o(\Delta u)\\ &=f'(u)g'(x)\Delta x+f'(u)\cdot o(\Delta x)+o(\Delta u) \end{align} \] 所以 \[ \mathrm{d}y=f'(u)\mathrm{d}u=f'(u)g'(x)\mathrm{d}x \] 书中用导数定义微分，因此复合函数的微分法则就是由链式法则推出。但是我个人感觉这样的写法更自然好懂：既然我要的是线性近似，那么自变量$u$当然也可以被它自己的线性近似替代。

有了链式法则，我们就有了一阶微分形式不变性：对于上面的自变量的微分$\mathrm{d}u$，我们原先把它看作自变量的增量$\Delta u$，但是现在我们发现如果$u$又作为另外一个函数$g$的因变量，$\mathrm{d}u$可以直接被替换成它求微分的结果$g'(x)\mathrm{d}x$.

那既然对谁微分都是一样的形式，岂不是自变量就不重要了？所以$\mathrm{d}$无论出现在哪里都是一个意思，无论$y$对应的自变量是$x$还是$v$？

错。我们上面说的微分形式不变性是对于一阶微分而言的，对于二阶微分会是什么样的情况呢？

对于二阶导数，书中是这么写的 \[ f''(x)=\dfrac{\mathrm{d}}{\mathrm{d}x}\left(\dfrac{\mathrm{d}y}{\mathrm{d}x}\right)=\dfrac{\mathrm{d}^2y}{\mathrm{d}x^2} \]

看着也挺怪的，我们用微分写 \[ \begin{align} \mathrm{d}^2y&=\mathrm{d}(\mathrm{d}y)\\ &=\mathrm{d}(f'(x)\mathrm{d}x)\\ &=\mathrm{d}(f'(x))\mathrm{d}x+f'(x)\mathrm{d}(\mathrm{d}x)\\ &=(f''(x)\mathrm{d}x)\mathrm{d}x+f'(x)\mathrm{d}^2x\\ &=f''(x)\mathrm{d}x^2+f'(x)\mathrm{d}^2x \end{align} \]

好像多了一项$f'(x)\mathrm{d}^2x$？

这就是为什么微分形式不变性对于二阶微分不成立！二阶微分不但会受$\mathrm{d}x^{2}$影响，也会受$\mathrm{d^2}x$影响。

我们若是想得到二阶导数的形式，就必须把$x$看成自变量而不是一个可微的函数，我们实际上求的是对$\mathrm{d}x$的偏微分

\[ \left(\partial ^ 2 y\right) _ {\mathrm{d}x}=f''(x)\mathrm{d}x^2 \]

所以，二阶微分不具有形式不变性。

现在来说积分。这里直接跳过书上的“记作”论调，重新定义：积分就是微分的逆运算。回想起我们对微分的理解：微分就是把一个函数映射到一个“实数到函数的映射”（若嫌麻烦也可以理解成二元函数）上面。那么积分就是微分的逆映射。给一个实数到函数的映射（二元函数），就能对应回一个函数上。嗯？等等，微分这个映射并不是单射，不同的函数也可能有相同的微分。那怎么办呢？我们给它打个补丁：由于有相同微分的原函数互相都只相差某个常数，我们就把积分定义成一个实数到函数的映射对应一个函数集合。这个函数集合中的函数互相都只相差某个常数，我们就用$F(x)+C$来表示这个函数集合。

从定义立即可以得到，如果在区间$I$上可导函数$F(x)$的导函数为$f(x)$，对任一$x\in I$，都有 \[ \int \mathrm{d}F(x)=\int f(x)\mathrm{d}x=F(x)+C. \] 回到上面的复合函数，如果$f(u)$具有原函数$F(u)$，由微分形式不变性，有 \[ \int f(g(x))g'(x)\mathrm{d}x=\int f'(u)\mathrm{d}u=F(u)+C \] 这就是换元积分法中的第一类换元法。其实，这就是对被积表达式部分积分。

我们也可以反向操作：

令$t=\phi ^{-1}(x)$，则$x=\phi (t)$，有 \[ \int f(x)\mathrm{d}x=\int f(\phi (t))\mathrm{d}\phi (t)=\int f(\phi (t))\phi '(t)\mathrm{d}t \] 这就是换元积分法中的第二类换元法。

微分法则能启发我们计算积分，比如：对于在区间$I$上的可微函数$f(x)$和$g(x)$有 \[ \begin{aligned} \mathrm{d}\left[f(x)g(x)\right]&=f(x)\cdot \mathrm{d}g(x)+\mathrm{d}f(x)\cdot g(x)\\ &=f(x)g'(x)\mathrm{d}x+f'(x)g(x)\mathrm{d}x \end{aligned} \] 两边积分得 \[ \int \mathrm{d}\left[f(x)g(x)\right]=\int f(x)g'(x)\mathrm{d}x+\int f'(x)g(x)\mathrm{d}x \] 即 \[ \int f(x)g'(x)\mathrm{d}x=f(x)g(x)-\int f'(x)g(x)\mathrm{d}x \] 这就是分部积分法。也可以写成简洁形式 \[ \int u\mathrm{d}v=uv-\int v\mathrm{d}u \] 如果你想要理解这些积分法则，这里有一个线索：第一、第二类换元法对应的是复合函数，分部积分法对应的是两个函数的乘积运算。这个视频也许也能帮助你更直观地理解。

学积分的时候应该注意思考积分法则的逆运算（逆操作）是什么。如果能明白简单的积分形式是怎么变复杂的，看到复杂的积分也就不难化简了。上面这三种积分法则的逆运算是什么呢？

很容易发现第一类、第二类换元法是互为逆运算的。而分部积分法的逆运算是它自己 \[ \int u\mathrm{d}v=uv-\int v\mathrm{d}u=uv-\left(uv- \int u\mathrm{d}v \right)=\int u\mathrm{d}v \]

References:

积分中的魔法

积分有什么用呢？

要解释积分的用途，我们要提一个很经典的问题：求曲边梯形的面积。也就是说，我们想知道由两条垂直于$x$轴的直线，一条函数曲线$y = f(x)$和$x$轴围成区域的面积。

首先我们得岔开话题，先讲积分的一个有趣的性质。

我们学过拉格朗日中值定理（均值定理）：函数$f(x)$若在$[a,b]$内连续，$(a,b)$内可导，存在$\xi \in (a,b)$使 \[ f(b)-f(a)=f'( \xi )(b-a) \] 我们可以尝试把这个定理应用到原函数$F(x)$上 \[ F(b)-F(a)=F'( \xi )(b-a)=f( \xi )(b-a) \] 等式右边是什么意思呢？它看着像是长为$f(\xi )$宽为$b-a$的长方形的面积。

微积分的核心思想之一，是把宏观的、难以解决的问题转化为很多局部的、近似的问题。

我们可以这么写 \[ F(x+\Delta x)-F(x)=f( \xi )\Delta x \] 等式右边的意思是说，在一个很小的宽为$\Delta x$的区间内，其中一点$\xi$的函数值为长，$\Delta x$为宽围成的面积。

微积分的核心思想之二是极限。在不断趋近的过程中证明要多近有多近。

在这里我们首先要做的是趋近。证明当$\Delta x \to 0$时$f( \xi )\Delta x$可以任意的接近$\Delta x$为宽的那个区间内的曲边梯形面积。也就是说 \[ \Delta A=\lim_{\Delta x \to 0}{f( \xi )\Delta x} \] 好吧，这个证明有点冗长，有时间再补。

下一步，就是积。把区间$[a,b]$分成$n$份，每一份的宽度为$\Delta x = \frac{b-a}{n}$，左右端点为$[x_{i-1},x_i]$，有 \[ F(x_n)-F(x_{n-1})+F(x_{n-1})-F(x_{n-2})+\cdots+F(x_1)-F(x_0)=\sum ^{n}_{i=1}\left[f\left( \xi _{i}\right) \Delta x \right] \] 这时候，奇迹发生了： \[ F(x_n)-F(x_0)=F(b)-F(a)=\sum ^{n}_{i=1}\left[ f\left( \xi _{i}\right) \Delta x \right] \] 左边中间的项全部被消掉，这时候我们发现，等式左边跟$n$无关了。也就是说，我们可以自信地写下 \[ F(b)-F(a)=\lim_{n\to \infty}{\sum ^{n}_{i=1}{\frac{f\left( \xi _{i}\right) (b-a)}{n}}}=\lim_{n\to \infty}{\sum ^{n}_{i=1}{\Delta A_i}}=A \] 原本看上去不可能的问题，就这么被轻易解决了。

由于很多问题都可以用类似求曲边梯形的方法解答，我们专门给$F(b)-F(a)$分配了符号，并称之为$f(x)$在区间$[a,b]$上的定积分： \[ \int_{a}^{b} f(x)\mathrm{d}x=F(b)-F(a) \] 上面的性质也成了积分中值定理 \[ \int_{a}^{b} f(x)\mathrm{d}x=f( \xi )(b-a) \]

从等价无穷小到泰勒公式

启程

在第 1.7 节无穷小的比较中就介绍了等价无穷小：

如果 $\lim \dfrac{\beta}{\alpha}=1$，那么就说 $\beta$ 和 $\alpha$ 是等价无穷小，记作 $\alpha \sim \beta$.

比如 \[ \sin x \sim x \ (x\to 0) \] 等价无穷小有什么特别的，以至于要专门给他分配个符号呢？

由极限运算法则，如果 $\lim f(x)=A$，$\lim g(x)=B$，那么 \[ \lim[f(x)\cdot g(x)]=\lim f(x)\cdot \lim g(x)=A\cdot B \] 所以 \[ \lim_{x\to 0} f(x) = \lim_{x\to 0} f(x) \cdot \lim_{x\to 0}\dfrac{\sin x}{x} = \lim_{x\to 0} \left[ f(x) \cdot \dfrac{\sin x}{x} \right] \] 来看个实际用例： \[ \lim _{x\rightarrow 0}\dfrac{\sin x}{x^{3}+3x}=\lim _{x\rightarrow 0}\left( \dfrac{\sin x}{x^{3}+3x}\cdot \dfrac{x}{\sin x}\right) = \lim _{x\rightarrow 0}\dfrac{x}{x(x^{2}+3)} = \dfrac{1}{3} \] 常用的等价无穷小还有 \[ \begin{aligned} e^x-1&\sim x\ (x\to 0)\\ \ln (1+x)&\sim x\ (x\to 0) \end{aligned} \]

岔路

过了一段时间，你学到了拉格朗日中值公式。如果（省略）则 \[ f(b)-f(a)=f'( \xi )(b-a) \] 回到上面那个实际用例。我们可以说，由 $\sin x$ 在 $x=0$ 的某一去心邻域内可导，所以存在 $\xi \in \mathring{U}(0,x)$ 使得 \[ \sin x-\sin 0=\cos \xi(x-0) \] 当 $x\to 0$ 时有 \[ \lim_{x\to 0}\dfrac{\sin x}{x}=\lim_{x\to 0}\dfrac{\sin x-\sin 0}{x-0}=\lim_{x\to 0}\cos \xi=1 \] 看起来有点意思？还有更有意思的。

如果 $f(x)$ 和 $g(x)$ 在 $a$ 的某去心邻域内可导，当 $x\to a$ 时函数 $f(x)$ 和 $g(x)$ 都趋于零，对于下面这个极限 \[ \lim_{x\to a}\frac{f(x)}{g(x)} \] 我们可以把上面的方法同时应用到分子分母上。我们为了连续性假定 $f(a)=g(a)=0$ 则此时两函数在 $a$ 的某邻域内连续。

存在 $\xi_1 \in \mathring{U}(a,x), \xi_2 \in \mathring{U}(a,x)$ 使得 \[ \begin{aligned} f(x)-f(a)&=f'(\xi_1)(x-a)\\ g(x)-g(a)&=g'(\xi_2)(x-a) \end{aligned} \]

若 $g'(x)\neq 0$，有 \[ \lim_{x\to a}\dfrac{f(x)}{g(x)}=\lim_{x\to a}\dfrac{f(x)-f(a)}{g(x)-g(a)}=\lim_{x\to a}\frac{f'(\xi_1)(x-a)}{g'(\xi_2)(x-a)}=\lim_{x\to a}\frac{f'(x)}{g'(x)} \] 洛必达法则！实际上证明洛必达法则并不依赖柯西中值定理。

上面的推导启示我们，洛必达法则和等价无穷小有某种意义上的联系。若函数 $f(x)$ 和 $g(x)$ 在 $x=x_0$ 的某邻域内 $n$ 阶可导，且当 $x\to x_0$ 时 $f(x)\sim g(x)$ 则 \[ \lim_{x\to x_0}\dfrac{f(x)}{g(x)}=\lim_{x\to x_0}\frac{f^{(n)}(x)}{g^{(n)}(x)}=1 \] 另外，在这个过程中你可能会发现 \[ \frac{f(b)-f(a)}{g(b)-g(a)}=\frac{f'(\xi_1)(b-a)}{g'(\xi_2)(b-a)}=\frac{f'(\xi_1)}{g'(\xi_2)} \] 柯西中值定理？其实并不是，柯西中值定理还需要 $\xi_1=\xi_2$，构造 \[ h(x) = [f(x) - f(a)][g(b) - g(a)] - [g(x) - g(a)][f(b) - f(a)]. \] 显然 $h(a)=h(b)=0$，由罗尔中值定理得 \[ 0 = h'(\xi) = f'(\xi)(g(b) - g(a)) - g'(\xi)(f(b) - f(a)) \]

为什么同济高数书上要写成这么别扭的样子呢？ \[ h(x)=f(x)-\frac{f(b)-f(a)}{g(b)-g(a)}g(x) \] 我猜大概是为了强调 $g(b)-g(a)\neq 0$ 吧（由 $g'(x)\neq 0$ 推出）

再来看一个洛必达法则的证明：

若 $f, g : (a, b) \to R$ 在 $x_0 \in (a,b)$ 上可导，且 $f(x_0)=g(x_0)=0$，$g'(x_0)\neq 0$. 则 \[ \frac{f'(x_0)}{g'(x_0)}=\frac{\lim_{x\to x_0}{\frac{f(x)-f(x_0)}{x-x_0}}}{\lim_{x\to x_0}{\frac{g(x)-g(x_0)}{x-x_0}}}=\lim_{x\to x_0}{\frac{f(x)-f(x_0)}{g(x)-g(x_0)}}=\lim_{x\to x_0}{\frac{f(x)}{g(x)}} \] 这就证完了？能用一行证明，为什么上面要绕一大圈？

请注意洛必达法则的条件

当 $x\to x_0$ 时，函数 $f(x)$ 及 $g(x)$ 都趋于零.

在点 $x_0$ 的某去心邻域内，$f'(x)$ 及 $g'(x)$ 都存在且 $g'(x)\neq 0$.

$\lim_{x\to x_0}{\frac{f'(x)}{g'(x)}}$ 存在（或为无穷大）.

其中第 1、2 点都不一样，但是证明时假定了 $f(x_0)=g(x_0)=0$ 所以实际上第 1 点没有区别。最关键的是第 2 点：$f(x)$ 和 $g(x)$ 只需要在 $x_0$ 的某去心邻域可导，不需要在 $x_0$ 可导。与之相对应，公式中也是取两函数导数的比值的极限。

迷途

我们来看一道经典例题： \[ \lim_{x\to0}\left(\frac{e^x +xe^x}{e^x-1}-\frac{1}{x}\right) \] 你可能会这么写： \[ \begin{aligned} \lim_{x\to 0}\left(\frac{e^x +xe^x}{e^x-1}-\frac{1}{x}\right)&=\lim_{x\to 0}\frac{e^x +xe^x}{e^x-1} - \lim_{x\to 0}\frac{1}{x} \\ &=\lim_{x\to 0}\frac{e^x +xe^x}{e^x-1}\times \lim_{x\to 0}\frac{e^x-1}{x}-\lim_{x\to 0}\frac{1}{x} \\ &=\lim_{x\to 0}\left(\frac{e^x +xe^x}{e^x-1} \times \frac{e^x-1}{x}\right)-\lim_{x\to 0}\frac{1}{x} \\ &=\lim_{x\to 0}\left(\frac{e^x +xe^x}{x}-\frac{1}{x}\right) \\ &=\lim_{x\to 0}\frac{e^x +xe^x-1}{x} \\ &=\lim_{x\to 0}\left(2e^x-xe^x\right) \\ &=2 \end{aligned} \]

然而！答案是 $\frac{2}{3}$.

错在哪呢？其实第一步就错了，拆出来成了 $\infty -\infty$，而极限运算法则只在两极限存在时才成立，不能拆。如果你不是这么做的但是得到了错误的结果，请自行根据这篇文章对号入座。

辅导书和老师可能会告诉你，等价无穷小的用法仅限于极限值整体乘以 1 再代换！这种说法确实没错，但是事情是不是就这么简单地结束了呢？为什么有的情况下替换不会出现问题呢？

请看同济高数第 1-7 节定理 1: $\beta$ 和 $\alpha$ 是等价无穷小的充分必要条件为 \[ \beta=\alpha + o(\alpha) \] 可以看出，两个等价无穷小之间差了一个高阶无穷小。那么什么时候不能用等价无穷小呢？

就是除了无穷小以外的量全部都被消去的情况，这时候高阶无穷小才会左右极限的结果，而它会受到等价无穷小替换的影响而不准确。

也就是说

已知 $\lim_{x\to x_0}{\frac{\alpha_1}{\alpha_2}}$ 存在， $\alpha_1,\alpha_{2},\beta_{1},\beta_{2}$ 都是 $x\rightarrow x_0$ 的无穷小量，且 $\alpha_1\sim\beta_1$，$\alpha_{2}\sim\beta_{2}$.

若 $\lim_{x\rightarrow x_0}{\frac{\alpha_1}{\alpha_2}} \neq 1$ （两者的泰勒展开的第一项不相同），则 $\alpha_1-\alpha_2\sim \beta_1-\beta_2$;

若 $\lim_{x\rightarrow x_0}{\frac{\alpha_1}{\alpha_2}} \neq -1$（两者的泰勒展开的第一项不互为相反数），则 $\alpha_1+\alpha_2\sim\beta_1+\beta_2$.

终点

上面看似已经把等价无穷小的用法说清楚了，但是还有很多隐藏的问题。比如说，极限运算法则必须要两个极限存在才成立，那么如果我要求的极限本来就不存在呢？难道我每次用之前还要证明这个极限存在？

所以我们不如用回等价无穷小的充要条件 \[ \alpha \sim \beta \Leftrightarrow \beta=\alpha + o(\alpha) \] 等价替换永远是最直接、最少出错的。

而实际上我们用等价无穷小的时候几乎从来都是换成多项式函数，因为它好化简、好求极限。

又过了一段时间，你学到了泰勒公式，它是拉格朗日中值公式的推广（令 $n=2m$） \[ \begin{align} \sin \left(x\right)&= x-{\frac {x^{3}}{3!}}+{\frac {x^{5}}{5!}}-{\frac {x^{7}}{7!}}+\cdots +(-1)^{m-1}\dfrac{x^{2m-1}}{(2m-1)!}+o(x^{2m})\\ e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+\cdots +\frac{x^{n-1}}{(n-1)!} +o(x^n)\\ \ln(1+x)&=x-{\frac {x^{2}}{2}}+{\frac {x^{3}}{3}}-\cdots+(-1)^{n-1}\dfrac{1}{n}x^n+o(x^n) \end{align} \]

接下来不用多说了吧。用泰勒公式，别用等价无穷小。

后记：这篇文章写的很混乱，中途删了又写，写了又删。最后终于在高数期末考前仓促结尾，行文思路混乱，更别说严谨性。现在回头反思，总感觉自己太过于相信自己的所谓直觉，推导一番后又发现和目标不搭边。总结：想的太多，读的太少，算的更少。