数学知识（一）

· · 算法·理论

温馨提示：本篇含有大量 \LaTeX 公式，可能加载较慢！

一. 质数

定义

若一个正整数的因数只有 1 和它本身，那么这个数就是质数，否则为合数。特殊的，1 既不是质数，又不是合数。

质数分布定理

\lim\limits_{n\rightarrow \infty}\pi(n) = \frac{n}{\ln n}

用人话来说就是当 n 趋近正无穷时，不超过 n 的质数大约有 \frac{n}{\ln n} 个。

质数的判定

如何判定一个正整数 n 是不是质数？

试除法

从定义出发，枚举 2\sim \lfloor\sqrt n\rfloor 的整数，一个一个试能不能整除。若能则为合数，否则为质数。

\texttt{Code:} 
bool check(int n) {
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i++)
        if(n % i == 0) return false;
    return true;
}

分解质因数

算数基本定理

内容：

任何一个大于 1 正整数都能唯一分解成有限个质数的乘积，可写作：

x = p_{1}^{\alpha_1}\times p_{2}^{\alpha_2}\times\cdots\times p_{k}^{\alpha_n}

在分解质因数时也可以用试除法，枚举 2\sim \lfloor\sqrt n\rfloor 的整数，若找到了一个能整除的数，就把它从 n 中除尽，这样就能保证后面满足这个条件的数一定是质数，就不用额外判断是不是质数了。

\texttt{Code:} 
for(int i = 2; i <= n / i; i++) {
    int s = 0;
    while(n % i == 0) n /= i, s++; //除尽
    if(s > 0) printf("%d %d\n", i, s);
}
if(n > 1) printf("%d %d\n", n, 1); //可能会剩下一个比较大的质因子

质数筛

1. 埃氏筛

思路：

把找到的质数的所有不大于 \sqrt n 的倍数全都筛掉，剩下的就全是质数了。 但是，同一个数会被它的不同质因子都筛一遍，效率有所降低。

时间复杂度：O(n\log\log n)。

代码：

void ai(int n) {
    for(int i = 2; i <= n; i++) {
        if(!st[i]) {
            primes[++tt] = i;
            for(int j = 2; i * j <= n; i++) st[i * j] = true;
        }
    }
}

2. 欧拉筛（线性筛）

思路：

在埃氏筛的基础上进行了优化，保证每个合数只会被它的最小质因子筛掉，时间复杂度有所降低。

时间复杂度：O(n)。

代码：

void ol(int n) {
    for(int i = 2; i <= n; i++) {
        if(!st[i]) primes[++tt] = i;
        for(int j = 1; j <= tt && i * primes[j] <= n; j++) {
            st[i * primes[j]] = true; 
            if(i % primes[j] == 0) break; //确保primes[j]一定是i的最小质因子，则primes[j]一定也是i * primes[j]的最小质因子，这样就确保了每个合数只会被它的最小质因子筛掉 
        }
    }
}

二. 因数

对于一个数 x(x \in [2,+\infty))，可以写成如下形式:

x = p_{1}^{\alpha_1}\times p_{2}^{\alpha_2}\times\cdots\times p_{k}^{\alpha_k}

对于每一个因数 d，都可写成：

d = p_{1}^{\beta_1}\times p_{2}^{\beta_2}\times\cdots\times p_{k}^{\beta_k}

由排列组合知识可知，x 的约数个数 num(x) 为：

(\alpha_1 + 1)\times(\alpha_2 + 1)\times\cdots\times(\alpha_k + 1)

约数之和 sum(x) 为：

(p_{1}^0+p_{1}^1+p_{1}^2+ \cdots +p_{1}^{\alpha_1})\times (p_{2}^0+p_{2}^1+p_{2}^2+\cdots+p_{2}^{\alpha_2})\cdots\times (p_{k}^0+p_{k}^1+p_{k}^2+ \cdots +p_{k}^{\alpha_k})

根据等比数列求和公式可得：

sum(x) = \prod\limits_{i = 1}^k\frac{p_i^{\alpha_i + 1} - 1}{p_i - 1}

试除法分解因数

因为一个数 n 的因数个数为 O(\sqrt n)，所以时间复杂度为 O(\sqrt n)。

\texttt{Code:} 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;

vector <int> get(int x) {
    vector <int> res;
    for(int i = 1; i <= x / i; i++) {
        if(x % i == 0) {
            res.push_back(i);
            if(i != x / i) res.push_back(x / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        vector <int> ans = get(x);
        for(auto i : ans) printf("%d ", i);
        puts("");
    }

    return 0;
}

最大公因数

定义：

若 d \mid a 且 d \mid b，则 d 是 a,b 的公因数，其中满足条件的最大的 d 就是最大公因数，记为 \gcd(a, b)。

最小公倍数

定义：

若 a \mid m 且 b \mid m，则 m 是 a,b 的公倍数，其中满足条件的最小的 m 就是最小公倍数，记为 \operatorname{lcm}(a, b)。

几个有意思的定理

证明：

考虑将 a,b 分解质因数，并将质因数对齐，得：

a = p_{1}^{a_1}p_{2}^{a_2}\cdots p_{k}^{a_k} b = p_{1}^{b_1}p_{2}^{b_2}\cdots p_{k}^{b_k}

再将 \gcd(a, b) = fac 和 \operatorname{lcm}(a, b) = m 分解质因数，得：

fac = p_{1}^{c_1}p_{2}^{c_2}\cdots p_{k}^{c_k} m = p_{1}^{d_1}p_{2}^{d_2}\cdots p_{k}^{d_k}

注意！这里的 a_i,b_i,c_i,d_i 可能为 0！（因为可能不含此质因子）

根据定义可知：

c_i = \min(a_i, b_i),d_i = max(a_i, b_i),i\in [1, k]

对于每个质因子 p_i 来看，d 与 m 相乘即为：

p_i^{\min(a_i, b_i)}\cdot p_i^{\max(a_i, b_i)} = p_i^{a_i + b_i}

所以总的乘起来就是 a\cdot b。

证明完毕。

由 $1$ 可知，只用知道其中一种的计算方法就可以直接推出另一种，所以只用考虑 $\gcd$ 该怎么计算。 若直接朴素计算 $\gcd$，最先想到的方式就是分解出其中一个数的所有因数，然后找最大的且能整除另一个数的因子，时间复杂度 $O(\sqrt n)$。 还有更快的方法吗？ ### 九章算术 · 更相减损术 #### 内容： $$\forall a, b\in \mathbb{N},a\ge b,\text{有} \gcd(a, b) = \gcd(b, a - b) = \gcd(a, a - b)$$ >#### 证明： > >对于 $a,b$ 的任意公因数 $d$，由于 $d \mid a,d \mid b$，所以 $d \mid (a - b)$。因此，$d$ 也是 $b, a - b$ 的公因数。所以 $a,b$ 的公因数集合与 $b, a - b$ 的公因数集合相同，那么最大公因数自然也就相同。对与 $a,a - b$ 同理。 > >证明完毕。 这种方法当 $a,b$ 相差不大时效率较高，但差距一旦过大，一直减也减不完，效率大打折扣。 但是这个方法可以扩展到 $n$ 个数，即： $$\gcd(a_1, a_2,\cdots ,a_n) = \gcd(a_1, a_2 - a_1, a_3 - a_2,\cdots ,a_n - a_{n - 1})$$ ### 欧几里得算法 我们发现上一种方法一次一次地减效率太低了，干脆一次就减完，即取模。 欧几里得算法就是在这个方面进行了优化。 #### 内容： $$\forall a, b\in \mathbb{N},b \ne 0, \gcd(a, b) = \gcd(b, a \bmod b)$$ #### 证明： 和上一种方法如出一辙。 >若 $a < b$，则上式显然成立。 > >若 $a\ge b$，不妨设 $a = k\cdot b + r$，其中 $0\le r < b$。显然 $r = a \bmod b$。 > >对于 $a,b$ 的任意公约数 $d$，由于 $d \mid a,d \mid (k\cdot b)$，所以 $d \mid (a - k\cdot b)$，即 $d \mid r$。因此 $d$ 也是 $b,r$ 的公因数。所以 $a,b$ 的公因数集合和 $b,a\bmod b$ 的公因数集合相同，最大公约数自然也就相等了。 > >证明完毕。 每次我们将 $\gcd(a, b)$ 变成了 $\gcd(b, a\bmod b)$，分析一下括号里两个变量的变化。 1. 当 $a < b$ 时，$\gcd(a, b)\rightarrow \gcd(b, a)$，就变成下面情况 $2$ 或 $3$。 2. 当 $b\le a < 2b$ 时，$\gcd(a, b) = \gcd(b, a - b)$ 进一步分析就会发现，括号中的第二个元素至少减少了一半。 3. 当 $a\ge 2b$，括号中的第二个元素 $b\rightarrow a\bmod b$ 一定小于 $b$ 也至少减少了一半。 综上所述，每次迭代第二个元素都会至少减半，所以时间复杂度是 $\log$ 级别的。具体的，时间复杂度应该是 $O(\log\max(a, b))$。 一般的，对于多个数 $a_1,a_2,\cdots, a_n$，做欧几里得算法的时间复杂度为 $O(n + \log\max\limits_{1\le i\le n}\{a_i\})$。 直接上代码： ```cpp int gcd(int x, int y) { //最大公因数 if(y == 0) return x; return gcd(y, x % y); } int lcm(int x, int y) { //最小公倍数 return x * y / gcd(x, y); } ``` ### $\texttt{update：}

一种求 n 个大数的 \operatorname{lcm} 的做法。（因为这个导致我模拟赛遗憾爆零）

题目：

给定 n 个正整数 \{a_1, a_2,\cdots,a_n\}，求它们的最小公倍数，结果对 998244353 取模。

数据范围：n\le 5000,1\le a_i\le 10^{18}。

首先要声明一点，不能在做 \operatorname{lcm} 时顺便取模！

知道了这一点后，要么使用高精度算 \gcd，要么就用接下来的优美方法。

鉴于高精度除法和取模太难写，在考场上很难写对，所以学习优美的另一种算法。

维护 \operatorname{lcm}(a_1, a_2,\cdots,a_i) = b_1\times b_2\times\cdots \times b_i，当新加进来一个数 a_{i + 1} 时，推式子：

&= \operatorname{lcm}(\operatorname{lcm}(a_1, a_2,\cdots,a_i), a_{i + 1})\\ &=\operatorname{lcm}(b_1\times b_2\times\cdots\times b_i,a_{i + 1})\\ &=b_1\times b_2\times\cdots\times b_i\times\frac{a_{i + 1}}{\gcd(b_1\times b_2\times\cdots\times b_i\bmod a_{i + 1}, a_{i + 1})} \end{aligned}

这里的 b_1\times b_2\times\cdots\times b_i\bmod a_{i + 1} 每次都要计算，所以时间复杂度为 O(n\log V + n^2)，其中 V 表示值域。

\texttt{Code:} 
#include <iostream>
using namespace std;
typedef unsigned long long ull;
const int N = 5010, mod = 998244353;
int n;
ull a[N], b[N];

inline ull gcd(ull a, ull b) {
    if(!b) return a;
    return gcd(b, a % b);
}

int main() {
    scanf("%d", &n);
    ull x;
    for(int i = 1; i <= n; i++) {
        scanf("%llu", &x);
        ull mul = 1;
        for(int j = 1; j < i; j++)
            mul = (__int128)mul * b[j] % x;
        b[i] = x / gcd(mul, x);
    }
    ull res = 1;
    for(int i = 1; i <= n; i++)
        res = (__int128)res * b[i] % mod;
    printf("%llu", res);
    return 0;
}

欧拉函数

定义：

欧拉函数就是指对于 m 来讲，在 1 \sim m 中与 m 互素的数的个数，例如，当 n = 8 时，与 8 互质的数分别是 1,3,5,7，因此 \varphi(8) = 4。

对于 \{p_n\},\{\alpha_n\}, m\in N_{\pm} 来讲，满足 m=\textstyle \prod\limits_{1\leq j\leq n}^{n}p_{j}^{\alpha_{j}} （即 {p_{n}} 为其质因子)

\varphi(m)=m\cdot\prod\limits_{1\leq j\leq n}^{n}\left(1-\textstyle{\frac{1}{p_j}}\right).

证明在这里

套公式代码：（时间复杂度：O(\sqrt n)）

#include <iostream>
using namespace std;
int n;
int main() {
    scanf("%d", &n);
    while(n--) {
        int x;
        scanf("%d", &x);

        int res = x;
        for(int i = 2; i <= x / i; i++) { //分解质因数
            if(x % i == 0) {
                res = res / i * (i - 1);
                while(x % i == 0) x /= i;
            }
        }
        if(x > 1) res = res / x * (x - 1);

        printf("%d\n", res);
    }
    return 0; //直接套公式也没什么好说的
}

若要求 1\sim n 中所有数的欧拉函数，一个一个求的时间复杂度为 O(n\sqrt n)，效率较低。

其实可以在线性筛质数时顺便求欧拉函数。

首先需要了解积性函数。

定义：

#### 基本性质： 若 $f$ 是积性函数，则 $n = \prod\limits_{i = 1}^m p_i^{c_i}$，则 $f(n) = \prod\limits_{i = 1}^m f(p_i^{c_i})$。 证明： >将 $n$ 分解质因数，对每个质因子都使用积性函数的定义，此性质显然成立。 #### 接着我们需要欧拉函数的几个性质： 1. 欧拉函数是积性函数。 2. 设 $p$ 为质数，若 $p \mid n$ 且 $p^2 \mid n$，则 $\varphi(n) = \varphi(\frac{n}{p})\cdot p$。 3. 设 $p$ 为质数，若 $p \mid n$ 且 $p^2 \nmid n$，则 $\varphi(n) = \varphi(\frac{n}{p})\cdot (p - 1)$。 #### 证明： **性质 $1$：** > >要证欧拉函数是积性函数，即证：有 $a, b$ 互质且有 $\varphi(ab) = \varphi(a)\cdot \varphi(b)$。 > >因为 $\gcd(a, b) = 1$，所以 $a, b$ 的质因数一定没有一个相同，将 $a,b$ 分解质因数。 > >设 > >$$a = p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$$ > >$$b = q_1^{d_1}q_2^{d_2}\cdots q_m^{d_m}$$ > >则 > >$$\varphi(a) = a\cdot (1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots (1 - \frac{1}{p_k})$$ > >$$\varphi(b) = b\cdot (1 - \frac{1}{q_1})(1 - \frac{1}{q_2})\cdots (1 - \frac{1}{q_m})$$ > >而 > >$$\varphi(ab) = (ab)\cdot [(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots (1 - \frac{1}{p_k})]\cdot [(1 - \frac{1}{q_1})(1 - \frac{1}{q_2})\cdots (1 - \frac{1}{q_m})]$$ > >$\therefore\varphi(ab) = \varphi(a)\cdot \varphi(b)$。 > >性质 $1$ 得证。 **性质 $2$：** >若 $p \mid n$ 且 $p^2 \mid n$，则 $n,\frac{n}{p}$ 拥有相同的质因子，只是指数不同罢了，但是欧拉函数的计算只看有没有这个质因子而不关心指数。设 $n,\frac{n}{p}$ 的质因子都为 $p_1, p_2,\cdots ,p_k$，则 > >$$\varphi(n) = n\cdot (1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots (1 - \frac{1}{p_k})$$ > >$$\varphi(\frac{n}{p}) = \frac{n}{p}\cdot (1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots (1 - \frac{1}{p_k})$$ > >两者相除，商为 $p$。 >性质 $2$ 得证。 **性质 $3$：** > >若 $p \mid n$ 但 $p^2 \nmid n$，则 $n,\frac{n}{p}$ 互质，根据性质 $1$ 可得 $\varphi(n) = \varphi(\frac{n}{p}) \cdot\varphi(p)$，而 $\varphi(p) = p - 1$，所以 $\varphi(n) = \varphi(\frac{n}{p})\cdot (p - 1)$。 > >性质 $3$ 得证。 综上所述，我们可以把上述性质与线性筛法结合起来。 具体地，每个合数 $x$ 只会被它的最小质因子 $p$ 筛一次，恰好在此时判断，从 $\varphi(\frac{x}{p})$ 递推到 $\varphi(n)$。 时间复杂度为 $O(n)$。 ```cpp void get_eulers() { phi[1] = 1; for(int i = 2; i <= n; i++) { if(!st[i]) { prime[++cnt] = i; phi[i] = i - 1; //若是质数就直接求出欧拉函数 } for(int j = 1; j <= cnt && prime[j] <= n / i; j++) { st[i * prime[j]] = true; if(i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; //此时 primes[j] 是 i 的最小质因子，即此时满足性质 2 break; } phi[i * prime[j]] = phi[i] * (prime[j] - 1); //否则满足性质 3 } } } ``` --- ## 三. 同余 ### 概念: 数学上，同余（$\texttt{congruence modulo}$，符号: $\equiv$） 是数论中的一种等价关系。**当两个整数除以同一个正整数,若得相同余数，则两个整数同余。** ### 同余运算的常见性质 1. $a\equiv b\pmod p \Longleftrightarrow p \mid (a - b)
  1. a\equiv b\pmod m,a\equiv b\pmod n\Rightarrow a\equiv b\pmod {[m, n]}
  2. (k, m) = d, ka\equiv kb\pmod m\Rightarrow a\equiv b\pmod {\frac{m}{d}}

证明：

对于性质 1：

根据定义，设 a = k_1p + r,b = k_2p + r，所以 a - b = (k_1 - k_2)p，所以 p \mid (a - b)。

证毕。

对于性质 2：

根据性质 1 得：n \mid (a - b),m \mid (a - b)，所以 [m, n] \mid (a - b)，即 a\equiv b\pmod {[m, n]}

证毕。

对于性质 3：

根据性质 1 得：m \mid k(a - b)，因为 \gcd(k, m) = d，所以 \frac{m}{d} \mid \frac{k}{d}(a - b)，又因为 \gcd(\frac{m}{d},\frac{k}{d}) = 1，所以 \frac{m}{d} \mid (a - b)，即a\equiv b\pmod {\frac{m}{d}}。

证毕。

基本知识 —— 关于 \bmod

由对于模 n 同余的所有整数组成的这个集合称为同余类（\texttt{congruence class} 或 \texttt{residue class}），或称剩余类。

可知，模 n 的同余类一共有 n 个，分别是模 n\equiv 0,1,\cdots n - 1 的这 n 个。

如果模 m 的一个剩余类里所有数都与 m 互素，就把它叫做与模 m 互素的剩余类，比如: 5 的一个剩余系为 \{4, 9, 14, \cdots ,5k+4(k \in \mathbb{Z})\}，其中所有数都与 5 互素，所以此剩余系是与 5 互素的剩余系。

从模 n 的每个剩余类中各取一个数，得到一个由 n 个数组成的集合，叫做模 n 的一个完全剩余系，简称完系。

显然，完系中的 n 个数分别属于 n 个不同的剩余类。比如 \{0,1,2,3,4\} 是 5 的一个完系，\{5,6,7,8,9\} 也是 5 的一个完系。

最简单的模 n 的完全剩余系是 \{1,2,3,\cdots,n-1\} 也叫作模 n 的最小非负完系。

简化剩余系( \texttt{reduced residue system} ) 也称既约剩余系或缩系，在与模 m 互素的全体剩余类中，从每一个类中各任取一个数作为代表组成的集合，叫做模 m 的一个简化剩余系。

有无穷多个简化剩余系。例如，模 5 的一个简化剩余系是 \{1,2,3,4\}，模 10 的一个简化剩余系是 \{1,3,7,9\}，模 18 的一个简化剩余系是 \{1,5,7,11,13,17\}。

m 的完全剩余系中与 m 互素的数构成的子集也是缩系。

此时欧拉函数的真正定义才浮出水面：

欧拉函数（ \texttt{Euler's totient function} ）是对于任意正整数其最小非负完系的个数，用 {\varphi} 来表示，即当我们用

$$\varphi(m) = s$$

费马小定理

内容：

若 p 是质数，则对于任意整数 a，有 a^{p}\equiv a\space (\bmod\space n)。

欧拉定理

内容：

若正整数 x, n 互质，则 x^{\varphi(n)}\equiv 1\space (\bmod\space n)，其中 \varphi(n) 为欧拉函数。

证明：

设 \{a_1, a_2,\cdots ,a_{\varphi(n)}\} 是 n 的一个缩系，且 1\le a_1,a_2,\cdots ,a_{\varphi(n)}\le n，换句话说，这些数都是 1\sim n 中与 n 互质的数，且两两不同。

又 \because x, n 互质。

$\therefore$ 集合 $\{xa_1, xa_2,\cdots ,xa_{\varphi(n)}\}$ 和集合 $\{a_1, a_2,\cdots ,a_{\varphi(n)}\}$ 在模 $n$ 的条件下完全等价，即： $$(xa_1)(xa_2)\cdots (xa_{\varphi(n)}) \equiv a_1a_2\cdots a_{\varphi(n)}\pmod n$$ $$\therefore x^{\varphi(n)}(a_1a_2\cdots a_{\varphi(n)})\equiv a_1a_2\cdots a_{\varphi(n)}\pmod n$$ 这里就要用到一个同余运算的法则了：若 $ac\equiv bc\space (\bmod\space n)$，且 $\gcd(c, n) = 1$，那么 $a\equiv b$。 证明：根据同余的定义，原式可以写成 $ac - kn = bc - tn\space (k,t\in \mathbb{Z})$，整理得：$(a -b)c = (k - t)n$。 $\therefore$ $\text{LHS}$ 需要含有因子 $n$。 又 $\because \gcd(c, n) = 1$。 $\therefore n \mid (a - b)

即 a\equiv b，证明完毕。

回到原题，由于 a_1,a_2,\cdots ,a_{\varphi(n)} 都与 n 互质，所以 a_1a_2\cdots a_{\varphi(n)} 也与 n 互质，则可以消掉，得到 x^{\varphi(n)}\equiv 1\space (\bmod\space n)。

\texttt{Q.E.D}

那么当模数 n 为质数时，由于 \varphi(n) = n - 1，所以费马小定理就是欧拉定理的一个特殊情况，也能得证。

裴蜀定理

内容：

对于任意整数 a,b，设 d = \gcd(a, b)，则对于所有整数 x,y 都有 d \mid (ax + by)。特别的，一定存在一对整数 x,y，满足 ax + by = d。

证明：

第一点是显然的，因为 d \mid a,d \mid b，所以 d \mid ax,d \mid by,d \mid (ax + by)。

对于第二点：

  1. 当 b = 0 时，显然当 x = 1, y = 0 时原式成立。

  2. 当 b > 0 时，则 \gcd(a, b) = \gcd(b, a\bmod b)。假设存在一对整数 x,y，满足 bx + (a\bmod b)y = \gcd(b, a\bmod b)，因为 bx + (a\bmod b)y = bx + (a - b\lfloor\frac{a}{b}\rfloor)y = ay + b(x - \lfloor\frac{a}{b}\rfloor y)，所以进一步令 x' = y, y' = x - \lfloor\frac{a}{b}\rfloor y，就得到了 ax' + by' = \gcd(a, b)。

接着对欧几里得算法的递归过程使用数学归纳法，可知第二点成立，也就是顺着欧几里得算法递归，最终会把 b 消成 0。

证明完毕。

P4549 【模板】裴蜀定理

这道题就考察对裴蜀定理的思考深度了。

先看两个数的情况，假如要最小化 a_1x_1 + a_2x_2 且要为正，根据裴蜀定理，原式的值一定是 \gcd(a_1, a_2) 的倍数，所以取 \gcd(a_1, a_2) 是最优的。

推广到 3 个数的情况，即最小化 a_1x_1 + a_2x_2 + a_3x_3 且为正，由上可知应最小化 \gcd(a_1, a_2) + a_3x_3，此式子的最小正值应该是 \gcd(\gcd(a_1, a_2), a_3) = \gcd(a_1, a_2, a_3)。

事实上，由于 \gcd(\gcd(a_1, a_2,\cdots ,a_{n - 1}), a_n) = \gcd(a_1, a_2,\cdots ,a_n)，所以是可以直接推广到 n 个数的，换句话说，原题的答案就是 \gcd(a_1, a_2,\cdots ,a_n)。

同时，裴蜀定理给出了整数 x,y 的计算方法，所以我们可以在执行欧几里得算法时顺便递归计算，这种计算方法被称为扩展欧几里得算法。

\texttt{Code:} 
int exgcd(int a, int b, int &x, int &y) {
    if(b == 0) {x = 1, y = 0; return a;}
    int xx, yy;
    int d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
}

注意 x,y 是引用传递，上述代码可求出二元一次不定方程 ax + by = \gcd(a, b) 的一组特解 x_0, y_0，并返回 \gcd(a, b)。

对于更一般的方程 ax + by = c，它有解当且仅当 d \mid c。所以在有解的情况下，先求出 ax + by = \gcd(a, b) 的一组特解 x_0,y_0，然后 x_0,y_0 同乘上 \frac{c}{d} 即是原方程的一组特解。

那么我们该怎么表示它的通解呢？

设 \gcd(a, b) = d。对于 ax + by = d，假设我们已经得到它的一组特解 x_0,y_0，那么我们考虑将 x0 加上 val 后得到另一组新整数解 x',y'，所以此时需要满足 b \mid (a\cdot val) 才行，即 val = k\cdot \frac{b}{d},k\in \mathbb{Z}，此时 y 应该减少 k\cdot \frac{a}{d}。

综上所述，ax + by = d 的通解为：

x = x_0 + k\cdot \frac{b}{d},\space \space \space \space y = y_0 - k\cdot \frac{a}{d}\space (k\in \mathbb{Z})

推广到一般情况 ax + by = c，通解为：

x = \frac{c}{d}x_0 + k\cdot \frac{b}{d},\space \space \space \space y = \frac{c}{d}y_0 + k\cdot \frac{a}{d}\space (k\in \mathbb{Z})

线性同余方程

定义：

形式化定义：形如：ax\equiv b\pmod p 的式子被称为线性同余方程，也称一次同余方程。

求解

根据同余运算的法则可得：p \mid (ax - b)，即 ax + py = b。根据裴蜀定理，此方程有解当且仅当 \gcd(a, p) \mid b。

在有解时，先用扩展欧几里得算法求出方程 ax + py = \gcd(a, p) 的一组特解 x_0,y_0，那么 x = \frac{b}{\gcd(a, p)}\cdot x_0 就是原方程的一个解，通解则是所有模 \frac{p}{\gcd(a, p)} 与 x 同余的整数。

乘法逆元

定义：

若整数 b, p 互质，并且 b \mid a，则存在一个整数 x，使得 \frac{a}{b}\equiv ax\pmod p。称 x 为 b 的模 p 乘法逆元，记为 b^{-1}\pmod p。

简单说来，逆元就是人们发现同余运算中有的时候会出现除法，而除法的计算又是比较复杂的，所以就想了一个办法将它转化为乘法，于是逆元应运而生。

因为 \frac{a}{b}\equiv ab^{-1}\equiv \frac{a}{b}\cdot b\cdot b^{-1}，所以 b\cdot b^{-1}\equiv 1\pmod p。

当 p 是质数且 b < p 时，根据费马小定理得：b^{p - 1}\equiv 1，所以 b\cdot b^{-1}\equiv b^{p - 1}，因为 b,p 互质，所以方程两边同时消去 b，得：

b^{-1}\equiv b^{p - 2}\pmod p

所以，当模数 p 为质数时，b^{p - 2} 即为 b 的乘法逆元。

意思是若模数时质数，就可以用快速幂来求逆元。

那么如果只保证 b,p 互质，那么就只能求解方程 bx\equiv 1\pmod p 得到逆元了。

P3811 【模板】模意义下的乘法逆元

若用上述方法一个一个地求逆元，时间复杂度为 O(n\log n)，在这道题 n\le 3\times 10^6 的超强数据下会光荣 TLE （其实快速幂加上巴雷特模乘能卡过）。

其实要快速求出 1\sim n 每个数的模 p（p 为质数）乘法逆元，有一种线性的做法。

设 p = ki + r,0\le r < p，即 p 除以 i 商 k 余 r。

所以有：

p\equiv ki + r\equiv 0\pmod p

时刻铭记我们的目标是 i^{-1}，所以得想办法把它创造并分离出来。

两边同乘上 i^{-1} 和 r^{-1}，得：

kr^{-1} + i^{-1}\equiv 0\pmod p

即

i^{-1} = -\lfloor\frac{p}{i}\rfloor\cdot (p\bmod i)^{-1}\pmod p

特别地，当 i = 1 时，i^{-1} = 1\pmod p。

然后就可以开始快乐地线性递推了。

\texttt{Code:} 
inv[1] = 1; //注意初始化
for(int i = 2; i <= n; i++)
    inv[i] = p - (p / i) * inv[p % i] % p;

P5431 【模板】模意义下的乘法逆元 2

若要求 n 个不连续的数的逆元，也要求线性，阁下又该如何应对？

注：以下所有运算都是在 \pmod p 的情况下进行。

设这 n 个数分别为 a_1,a_2,\cdots ,a_n。

那么它们的逆元分别为 \frac{1}{a_1},\frac{1}{a_2}\cdots ,\frac{1}{a_n}。

计算这 n 个数的前缀积 sum_1,sum_2,\cdots ,sum_n。

有递推式：

\frac{1}{sum_i} = \frac{1}{sum_{i + 1}}\cdot a_{i + 1}

而

\frac{1}{a_i} = \frac{1}{sum_i}\cdot sum_{i - 1}

所以我们可以先朴素求出 sum_n 的逆元，然后从后往前线性递推求出每个 sum_i 的逆元，进而求出 a_i 的逆元。

\texttt{Code:} 
    sum[0] = 1;
    for(int i = 1; i <= n; i++) {
        a[i] = read<ll>();
        sum[i] = (sum[i - 1] * a[i]) % p;
    }
    ll x0, y0;
    exgcd(sum[n], p, x0, y0);
    inv_sum[n] = (x0 % p + p) % p;
    for(int i = n - 1; i; i--)
        inv_sum[i] = (inv_sum[i + 1] * a[i + 1]) % p;
    ll tmp = k, res = 0;
    for(int i = 1; i <= n; i++) {
        res = (res + tmp * inv_sum[i] % p * sum[i - 1] % p) % p;
        tmp = tmp * k % p;
    }

中国剩余定理 \texttt{（CRT）}

内容：

设 m_1,m_2,\cdots ,m_3 是两两互质的整数，M = \prod\limits_{i = 1}^{n}m_i,M_i = \frac{M}{m_i},t_i 是线性同余方程 M_it_i\equiv 1\pmod {m_i} 的一个解。对于任意的 n 个整数 a_1,a_2,\cdots ,a_n，方程组

\begin{cases} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \\ \vdots \\ x\equiv a_n\pmod {m_n}\end{cases}

有整数解，解为 x = \sum\limits_{i = 1}^{n}a_iM_it_i，且在 0\sim M - 1 中有唯一解。

中国剩余定理不但给出了证明，还给出了一种构造方案来求解。

比如我们现在要求解一个方程组：

\begin{cases} x\equiv 2\pmod {3} \\ x\equiv 3\pmod {5} \\ x\equiv 2\pmod {7}\end{cases}

一个很暴力的做法就是挑一个方程来枚举 x，并一个一个检查它是否符合其他的方程。

但其实我们可以先求解这个方程：

（以下都讨论最小非整数解）

\begin{cases} x_1\equiv 1\pmod {3} \\ x_1\equiv 0\pmod {5} \\ x_1\equiv 0\pmod {7}\end{cases}

那么很明显 x_1 = 70，此时对于 3 个模数就表示为 (1, 0, 0)。

接着再解方程：

\begin{cases} x_2\equiv 0\pmod {3} \\ x_2\equiv 1\pmod {5} \\ x_2\equiv 0\pmod {7}\end{cases}

解得 x_2 = 21，此时对于 3 个模数就表示为 (0, 1, 0)。

同理，再解方程：

\begin{cases} x_3\equiv 0\pmod {3} \\ x_3\equiv 0\pmod {5} \\ x_3\equiv 1\pmod {7}\end{cases}

解得 x_2 = 15，此时对于 3 个模数就表示为 (0, 0, 1)。

我们想要求解的是模表示为 (2, 3, 2) 的情况怎么办呢？

很简单，我们将这个解的模的情况分解一下，其实就是：

(2, 3, 2) = 2\times (1, 0, 0) + 3\times (0, 1, 0) + 2\times (0, 0, 1)

那么原方程的解就是 x = 2\cdot x_1 + 3\cdot x_2 + 2\cdot x_3 = 233。

落在 0\sim M - 1 的范围就是 233\bmod 105 = 23。

这个神奇的构造方法就是 \texttt{CRT} 的核心。

证明：

考虑解 n 个方程组，其中第 i 个为：

\begin{cases} x_i\equiv 0\pmod {m_1} \\ x_i\equiv 0\pmod {m_2} \\ \vdots \\x_i\equiv 1\pmod {m_i}\\ \vdots \\ x_i\equiv 0\pmod {m_n}\end{cases}

也就是第 i 个方程组只对模的情况 (a_1,a_2,\cdots ,a_n) 的第 i 项 a_i 有影响，换句话说，第 i 个方程的模的情况为：(0, 0,\cdots ,1,\cdots ,0)，其中 1 位于第 i 个位置上。

可以把所有模为 0 的方程合并起来，得：

\begin{cases} x_i\equiv 0\pmod {\frac{M}{m_i}}\\ x_i\equiv 1\pmod {m_i}\end{cases}

设 M_i = \frac{M}{m_i}，即：

\begin{cases} x_i\equiv 0\pmod {M_i} & \cdots\space\cdots 1\\ x_i\equiv 1\pmod {m_i} & \cdots\space\cdots 2\end{cases}

根据 1 式，可设：x_i = t_iM_i,t_i\in \mathbb{Z}，再将其代入 2 式，得：

t_iM_i\equiv 1\pmod {m_i}

那么我们只需要将 t_i 解出来就行了，最后的解即为 x = \sum\limits_{i = 1}^{n}a_ix_i，同时由于所有 m_i 两两互质，所以方程 t_iM_i\equiv 1\pmod {m_i} 是有解的。

证毕。

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

直接套公式就行了，无需多言。

注意中间计算过程可能爆 long long，要开 __int128。

\texttt{Code:} 
#include <iostream>

using namespace std;
typedef long long ll;

const int N = 15;

int n;
__int128 MUL = 1;
ll a[N], b[N];
__int128 M[N], t[N];
ll res;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {x = 1, y = 0; return a;}
    ll xx, yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - yy * (a / b);
    return d;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld%lld", &a[i], &b[i]);
        MUL *= a[i];
    }
    for(int i = 1; i <= n; i++) {
        M[i] = MUL / a[i];
        ll x0, y0;
        exgcd(M[i], a[i], x0, y0);
        t[i] = (x0 % a[i] + a[i]) % a[i];
        res = (res + (__int128)((b[i] * M[i]) % MUL * t[i]) % MUL) % MUL;
    }
    printf("%lld", res);
    return 0;
}

但是我们发现这个算法局限性太高，因为它有一个很大的限制条件：m_i 两两互质，但凡有一个不满足都不行，而这种条件一般很难见到，所以我们还需要一种更加通用的解法。

它就是：扩展中国剩余定理 （\texttt{exCRT}）。

扩展中国剩余定理 （\texttt{exCRT}）

由于中国剩余定理已不再适用，所以我们要另寻出路。

方程组是由很多个模线性同余方程构成的。假设我们能把两个模线性同余方程组，等价地合并成一个方程，问题就迎刃而解了——只需要不停地合并这些方程，只到只剩下一个。

——阮行止

接下来考虑如何合并两个同余方程：

若现在要合并以下两个方程：

\begin{cases} x\equiv a\pmod {p_1} \\ x\equiv b\pmod {p_2}\end{cases}

根据同余运算的定义，令：

x = k_1p_1 + a = k_2p_2 + b

整理一下，得：

k_1p_1 - k_2p_2 = b - a

由于我们想求出最小非负整数 x，所以需要求出 k_1 或 k_2,并使其最小，这里不妨对 k_1 下手。

设 d = \gcd(k_1, k_2)，通过 \operatorname{exgcd} 可解出方程 k_1p_1 - k_2p_2 = d 的一组特解 t_1, t_2，则通解表示为：

\begin{cases} t_1' = t_1 - \frac{p_2}{d}k \\ t_2' = t_2 + \frac{p_1}{d}k\end{cases}

其中 k\in \mathbb{Z}。

又因 k_1 = \frac{b - a}{d}\cdot t_1'，所以要想最小化 k_1，就要最小化 t_1'，设 t_1' 的最小值为 t_0，则 t_0 = t_1\bmod \frac{p_2}{d}。

于是就可以将两个同余方程合并为：

x\equiv p_1\frac{b - a}{d}t_0 + a\pmod {\operatorname{lcm}(p_1, p_2)}

写代码时要注意几点：

  1. 判无解；
  2. 及时取模并避免负数
  3. 防止中间计算过程爆 long long，要么用龟速乘要么用 __int128。
\texttt{Code:} 
#include <iostream>

using namespace std;
typedef long long ll;

int n;
ll a, b;
ll p1, p2;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {x = 1, y = 0; return a;}
    ll xx, yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - yy * (a / b);
    return d;
}

void merge(ll &a, ll &p1, ll b, ll p2) {
    if(a == -1 && p1 == -1) return ;
    ll x0, y0;
    ll d = exgcd(p1, p2, x0, y0);
    if((b - a) % d != 0) {a = p1 = -1; return ;}
    p2 /= d;
    ll t0 = (__int128)((b - a) / d) % p2 * x0 % p2; //这里将 t0 和 (b - a) / d 先乘起来合并了
    //及时取模，可能会爆 long long，开 __int128
    while(t0 < 0) t0 += p2; //防负数
    a += p1 * t0;
    p1 *= p2;
}

int main() {
    scanf("%d", &n);
    a = 0, p1 = 1;
    while(n--) {
        scanf("%lld%lld", &p2, &b);
        merge(a, p1, b, p2);
    }
    printf("%lld", a);
    return 0;
}