一篇测试文章，用于测试公式、代码、图片、表格等内容是否显示正确。

数学公式测试

约数之和

求一系列数的乘积所得到的数的所有的约数之和。

先对每个数做素因数分解，然后使用生成函数的思想，可知最后的结果为

ans = \prod_{i = 1}^{k}\sum_{j = 0}^{\alpha_i}p_{i}^j

根据数据范围，选择使用秦九韶算法，分治或者等比数列求和公式进行计算即可。

最大公约数

辗转相除

最常用的方法。

更相减损

弱化版的辗转相除。

高精度gcd

高精度gcd常用更相减损术去做，因为高精度的取模不好写。

互素与欧拉函数

欧拉函数的定义是： $\phi(x)$ 定义为 $1$ 到 $x$ 中与 $x$ 互素的数的个数。

容易发现，对素数 $p$ 来说， $\phi(p) = p - 1$ 。

$\phi(x)$ 的计算公式容易理解：

\phi(x) = x \times(1 - \frac{1}{p_1})\times(1 - \frac{1}{p_2})...\times(1 - \frac{1}{p_k})

可以从概率的角度/容斥原理的角度去考虑这个公式（有多大概率取到不是 $p_i$ 的倍数的数）。

考虑 $c = a\times b$ ，如果有 $\gcd(a, b) = 1$ ，则由上述计算公式中，可以发现 $\phi(c) = \phi(a)\times \phi(b)$ （因为没有相同素因子）

如果 $\gcd(a,b) \ne 1$ ，倘若 $a$ 为素数，那么也是有很好的性质的。因为 $a$ 为素数，且 $\gcd(a, b) \neq 1$ ，所以 $\gcd(a, b) = a$ ，考虑到 $\phi(a)$ 和 $\phi(b)$ 的计算式，可以发现 $\phi(c) = a \times \phi(b)$ 。

利用线性筛，可以 $O(n)$ 的时间预处理出 $\phi(x)$ 。

约数函数

约数函数 $d(n)$ 的含义是 $n$ 的约数个数（包括 $1$ 和 $n$ 本身）。

约数函数 $d(n)$ 的求法有很多：

枚举 $\sqrt n$ 以内的约数，复杂度 $O(\sqrt n)$ 求出 $d(n)$ 。
贡献法，枚举约数 $i$ ，枚举倍数 $j$ ，则 $i \times j$ 的一个约数就出来了，复杂度 $O(n\log n)$ 求出所有的 $d(1)$ 到 $d(n)$ 。
筛素数的过程中求积性函数，复杂度 $O(n\log \log n)$ 。
对 $n$ 做素因数分解，使用乘法原理，每个素因子次数为 $cnt$ 则有 $cnt + 1$ 种选法，乘起来就是约数个数。

同余

贝祖定理

若 $\gcd(a, b) = d$ ，那么存在整数 $x, y$ ，使得 $ax + by = d$ 成立。

显然，若 $d$ 不能整除 $c$ ，那么 $ax + by = c$ 一定没有整数解。

特殊地， $\gcd(a, b) = 1$ 时，存在整数 $x, y$ ，使得 $ax + by = 1$ 成立。

中国剩余定理

普通CRT

对于同余方程组

\begin{cases} x\equiv a_1(mod\ m_1)\\ x\equiv a_2(mod\ m_2)\\ ...\\ x\equiv a_n(mod\ m_n)\\ \end{cases}

其中 $\gcd(m_i, m_j) = 1$ ， $1\leq i, j\leq n,i \neq j$

设 $M = \prod\limits_{i = 1}^nm_i$ ， $M_i = \frac{M}{m_i}$ ， $M_i^{-1}M_i\equiv1(mod\ m_i)$

则 $x\equiv\sum\limits_{i= 1}^{n}M_i^{-1}M_ib_i(mod\ m_j),\forall 1\leq j\leq n$

即我们给出了一个构造 $x$ 的方式。容易验证上式成立。

在求 $M_i^{-1}$ 时，注意到 $\gcd(M_i^{-1}, m_i) = 1$ ，所以可以使用 exgcd 进行求解，而使用其他的方法求可能会求不出来（exgcd 只要有数和模数互素即可，而其他的方法需要模数是素数）。

exCRT

对于上述同余方程组，当不满足模数两两互素的时候，要想构造出 $x$ ，就需要使用扩展中国剩余定理了。

扩展中国剩余定理的思路是逐步两两合并方程：

\begin{cases} x\equiv a_1(mod\ m_1)\\ x\equiv a_2(mod\ m_2) \end{cases}

改写成等式：

\begin{cases} x = m_1p+a_1\\ x = m_2q+a_2 \end{cases}

需要有合适的整数使得 $p, q$ 都是整数，所以 $m_1p - m_2q = a_2 - a_1$ 要有整数解，所以 $\gcd(m_1, m_2)\mid(a_2 - a_1)$ 才能保证有合适的 $x$ 。

最大流

问题定义

有一个网络（有向图），网络中有一个源点（只有出边） $S$ 和一个汇点（只有入边） $T$ ，网络中每条边都有一个权值，代表这条边的容量。假设从 $S$ 开始源源不断地灌水，问 $T$ 点的最大流量是多少。

技术栈	说明	官网
React	用户界面库	链接
Vue.js	渐进式框架	链接
Angular	完整的框架	链接

求解

理论基础

这里不加证明地给出求解最大流问题的算法的理论基础。

残留网络：在原来的网络的基础上加上反向边，初始时反向边的容量是 $0$ ，在有流流过的时候，正向边的剩余容量减少 $d$ ，则反向边的容量增加 $d$ 。

增广路：从源点 $S$ 到汇点 $T$ 的一条路径，如果这条路径上每条边的容量 $-$ 实际流量 $>0$ ，则这条路径叫做增广路径。

可以证明，只要残留网络中能够找到增广路，那么流就可以通过这条增广路变得更大；反之，如果网络中没有增广路，那么网络的流量就已经达到了最大。但是这里不证明，可以去自行参考 OI-Wiki 或者其他相关书籍。

之所以要在残留网络而不是在原网络中找增广路，是因为在寻找增广路时有时可能需要“反悔”。一个用于解释的例子可以看这里

EK 算法

EK 算法的思路是：每次通过 bfs 找到残留网络中的任意一条增广路径，然后把这条路径能增加的流累加到结果上，并且把这条路径的正向和反向边的剩余容量更新。当找不到增广路径时，便是得到了最大流。

EK 算法求最大流的时间复杂度为 $O(nm^2)$ 。

EK 算法的代码实现以及细节解释：

模板题链接

#include <bits/stdc++.h>

using namespace std;

const int N = 1010; 
const int M = 20020; // 要维护残留网络，所以边数是两倍
const int INF = 1e8; // 需要设置成一个比最大流还要大的数

int h[N], e[M], ne[M], f[M], idx; // f[i] 表示编号为 i 的边的容量，i 和 i ^ 1 互为反向边，二者容量之和为实际容量
int n, m, S, T;
int pre[N], d[N]; // pre[i] 表示 bfs 时能走到编号为 i 的点的边的编号；d[i] 表示 bfs 时走到 i 点的路径的最小边权
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx++;
    e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx++;
}

bool bfs() {
    queue<int> q;
    memset(st, 0, sizeof st); // 记得每次 bfs 前清空状态
    q.push(S);
    d[S] = INF;
    st[S] = true;
    
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        
        for (int i = h[t]; i >= 0; i = ne[i]) {
            int ver = e[i];
            // 把之前没访问过且本条边有流的点加入到队列中
            if (!st[ver] && f[i]) {
                st[ver] = true;
                pre[ver] = i;
                d[ver] = min(d[t], f[i]);
                q.push(ver);
                if (ver == T) {
                    return true;
                }
            }
        }
    }
    return false;
}

int update() {
    // pre[i] 为走到 i 点的边的编号，pre[i] ^ 1 为走到 i 的前驱点的边的编号，e[pre[i] ^ 1] 为 i 的前驱点
    for (int i = T; i != S; i = e[pre[i] ^ 1]) {
        f[pre[i]] -= d[T];
        f[pre[i] ^ 1] += d[T];
    }
    // d[T] 就是这一轮求得的增广路贡献的流
    return d[T];
}

int EK() {
    int res = 0;
    while (bfs()) {
        res += update();
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    cout << EK() << "\n";
    
    return 0;
}

Dinic 算法

Dinic 算法的思想是：每次先把残留网络处理成分层图，在处理成分层图的过程中顺便看残留网络中是否还有增广路，如果还有增广路，则接下来对分层图进行深搜，深搜的时候可能会发现很多条能够走到汇点 $T$ 的路径，把这些路径的流加起来，就是本轮新增的流的大小。

Dinic 算法求最大流的时间复杂度为 $O(n^2m)$ 。

下面给出 Dinic 算法的代码模板：

原题链接

仅有满流优化版本：

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;
const int M = 200020;
const int INF = 1e8;

int h[N], e[M], ne[M], f[M], idx;
int n, m, S, T;
int level[N]; // 用于构建分层图 + bfs 判重数组

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx++;
    e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx++;
}

bool bfs() {
    queue<int> q;
    q.push(S);
    memset(level, -1, sizeof level);
    level[S] = 0;
    
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        
        for (int i = h[t]; i >= 0; i = ne[i]) {
            int ver = e[i];
            if (level[ver] == -1 && f[i]) {
                level[ver] = level[t] + 1;
                q.push(ver);
                // 每次不一定要把整个网络转化为分层图
                if (ver == T) {
                    return true;
                }
            }
        }
    }
    return false;
}

// 递归深搜从某个结点 u 开始，最多能流到 T 多少流量
int update(int u, int limit) {
    if (u == T) {
        return limit;
    }
    
    int flow = 0;
    // flow < limit 是重要优化，当前结点的流达到前面的 limit 时，其他后继结点就不能贡献了
    for (int i = h[u]; i >= 0 && flow < limit; i = ne[i]) {
        int ver = e[i];
        if (level[ver] == level[u] + 1 && f[i]) {
            int t = update(ver, min(limit - flow, f[i]));
            // 回溯回来记得更新残留网络
            flow += t;
            f[i] -= t;
            f[i ^ 1] += t;
        }
    }
    return flow;
}

int dinic() {
    int res = 0;
    while (bfs()) {
        res += update(S, INF);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    cout << dinic() << "\n";
    
    return 0;
}

有当前弧优化和废点优化版本：

最大流（测试主题与样式的文章）