GabWiki | GabWiki

数学

向上取整

$⌈ \frac{a}{b} ⌉ = ⌊ \frac{a + b - 1}{b} ⌋$ 。

C++

int ceil = (a + b - 1) / b

int ceil = (a + b - 1) / b

加法原理

完成一个工程可以有 $n$ 类办法， $a_{i} (1 \leq i \leq n)$ 代表第 $i$ 类方法的数目。那么完成这件事共有 $S = a_{1} + a_{2} + \dots + a_{n}$ 种不同的方法。

乘法原理

完成一个工程需要分 $n$ 个步骤， $a_{i} (1 \leq i \leq n)$ 代表第 $i$ 个步骤的不同方法数目。那么完成这件事共有 $S = a_{1} \times a_{2} \times \dots \times a_{n}$ 种不同的方法。

算术基本定理

任何一个大于 $1$ 的正整数都能分解为有限个质数的幂的乘积：

n = p_{1}^{α_{1}} \times p_{2}^{α_{2}} \times \dots \times p_{k}^{α_{k}}, p_{1} < p_{2} < \dots < p_{k}

其中 $α_{i} \in Z$ ， $p_{i}$ 都是质数，且 $p_{1} < p_{2} < \dots p_{k}$ ；在不计次序的意义下，该表示唯一。

裴蜀定理

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

其内容是：

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

平方和公式

\sum_{i = 1}^{n} i^{2} = 1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}

质数

试除法判质数

模板代码：

JavaC++

Java

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) return false;
    }
    return true;
}

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) return false;
    }
    return true;
}

C++

bool is_prime(int n) {
    if (n < 2) return false;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) return false;
    }
    return true;
}

bool is_prime(int n) {
    if (n < 2) return false;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) return false;
    }
    return true;
}

时间复杂度： $O (\sqrt{n})$ 。

试除法分解质因数

分解质因数（Prime Factorization）：根据算术基本定理，每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。

模板题：【数学】分解质因数。

原理：试除法，枚举 $2 \dots n$ 中的所有质数，如果 $i$ 是 $n$ 的质因子，就把 $n$ 中的 $i$ 除干净。

模板代码：

JavaC++

Java

void pf(int n) {
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            int s = 0;
            while (n % x == 0) {
                n /= x;
                ++s;
            }
            System.out.println(x + " " + s);
        }
    }
    if (n > 1) System.out.println(n + " 1");
}

void pf(int n) {
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            int s = 0;
            while (n % x == 0) {
                n /= x;
                ++s;
            }
            System.out.println(x + " " + s);
        }
    }
    if (n > 1) System.out.println(n + " 1");
}

C++

void pf(int n) {
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            int s = 0;
            while (n % x == 0) {
                n /= x;
                ++s;
            }
            printf("%d %d\n", x, s);
        }
    }
    if (n > 1) printf("%d 1\n", n);
}

void pf(int n) {
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            int s = 0;
            while (n % x == 0) {
                n /= x;
                ++s;
            }
            printf("%d %d\n", x, s);
        }
    }
    if (n > 1) printf("%d 1\n", n);
}

时间复杂度：

最差： $O (\sqrt{n})$ ；
最好： $O (\log N)$ 。

其中枚举的 $i$ 一定是质数，因为：当枚举到 $i$ 的时候，已经把 $[2, i - 1]$ 中的质因子都除掉了，当 if (n % i == 0) 成立的时候， $n$ 中已经没有任何在 $[2, i - 1]$ 范围内的质因子，又因为 $n$ 是 $i$ 的倍数，所以 $i$ 也没有任何在 $[2, i - 1]$ 范围内的因子，所以此时 $i$ 一定是质数。

筛质数

模板题：【数学】筛质数。

朴素筛

原理：

枚举 $x \in [2, n]$ ， $x$ 的倍数一定是合数，所以可以在枚举到 $x$ 的时候筛掉所有 小于等于 $n$ 的 $x$ 的倍数 。
而在枚举到 $p \in [2, n]$ 的时候，如果 $p$ 还没有被筛掉，说明 $p$ 不是 $x \in [2, p - 1]$ 中任意一个数的倍数，所以 $p$ 一定是质数。

模板代码：

Java

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[x]) primes[cnt++] = x;
        for (int k = 2; k * x <= n; ++k) isNotPrime[k * x] = true;
    }
    return cnt;
}

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[x]) primes[cnt++] = x;
        for (int k = 2; k * x <= n; ++k) isNotPrime[k * x] = true;
    }
    return cnt;
}

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

埃氏筛

原理：要得到自然数 $n$ 以内的全部质数，把不大于 $\sqrt{n}$ 的所有质数的倍数筛除，剩下的就都是质数。

证明：根据算术基本定理：每一个大于 $1$ 的正整数都能分解成有限个质数的幂的乘积，且由于是从小到大枚举，在枚举到某个合数之前，一定先会枚举到它的质因数，也就是说所有的合数都会被它的质因数筛掉。

模板代码：

Java

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[x]) {
            primes[cnt++] = x;
            for (int k = 2; k * x <= n; ++k) isNotPrime[k * x] = true;
        }
    }
    return cnt;
}

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[x]) {
            primes[cnt++] = x;
            for (int k = 2; k * x <= n; ++k) isNotPrime[k * x] = true;
        }
    }
    return cnt;
}

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

线性筛（欧拉筛）

原理：线性筛保证了每个合数都只被其最小质因子筛掉。

模板代码：

JavaC++

Java

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[i]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= n / x; ++i) {
            isNotPrime[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
    return cnt;
}

int countPrimes(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    for (int x = 2; x <= n; ++x) {
        if (!isNotPrime[i]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= n / x; ++i) {
            isNotPrime[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
    return cnt;
}

C++

int cnt, primes[N];
bool np[N];

int sieve(int n) {
    for (int x = 2; x <= n; ++x) {
        if (!np[x]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= n / x; ++i) {
            np[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
    return cnt;
}

int cnt, primes[N];
bool np[N];

int sieve(int n) {
    for (int x = 2; x <= n; ++x) {
        if (!np[x]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= n / x; ++i) {
            np[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
    return cnt;
}

时间复杂度： $O (N)$ 。

线性筛是如何保证每个合数只会被其最小质因子筛掉的？

当 x % primes[i] == 0 时，说明此时遍历到的 $p_{i}$ 不是 $x$ 的质因子，那么 ** $p_{i}$ 一定小于 $x$ 的最小质因子 **，所以 $p_{i} \cdot x$ 的最小质因子就是 $p_{i}$ ；
当 x % primes[i] != 0 时，说明 $x$ 的最小质因子是此时的 $p_{i}$ ，因此 $p_{i} \cdot x$ 的最小质因子依旧应该是 $p_{i}$ ，但如果继续枚举的话，我们就把 $p_{i + 1} \cdot x$ 这个数筛掉了，虽然这个数也是合数，但是筛掉它的时候并不是用它的最小质因数筛掉的 ，而是利用 $p_{i + 1}$ 和 $x$ 把它删掉的，而这个数的最小质因数其实是 $p_{i}$ ，如果不在这里退出循环的话，就会发现有些数是被重复筛了的。

勒让德定理

在正数 $n!$ 的质因数分解中，质数 $p$ 的指数记作 $ν_{p} (n!)$ ，则：

ν_{p} (n!) = \sum_{i = 1}^{⌊ \log_{p} n ⌋} ⌊ \frac{n}{p^{k}} ⌋

模板代码：

C++

int count(int n, int p) {
    int res = 0;
    while (n) res += n /= p;
    return res;
}

int count(int n, int p) {
    int res = 0;
    while (n) res += n /= p;
    return res;
}

约数

试除法求所有约数

模板代码：

C++

set<int> get_divisors(int n) {
    set<int> divisors;
    for (int i = 1; i <= n / i; ++i) {
        if (n % i == 0) {
            divisors.insert(i);
            divisors.insert(n / i);
        }
    }
    return divisors;
}

set<int> get_divisors(int n) {
    set<int> divisors;
    for (int i = 1; i <= n / i; ++i) {
        if (n % i == 0) {
            divisors.insert(i);
            divisors.insert(n / i);
        }
    }
    return divisors;
}

时间复杂度： $O (\sqrt{n})$ 。

int 范围内，约数最多的数其约数有 $1536$ 个。

约数个数

求约数个数

模板题：【数学】约数个数。

原理：

根据算术基本定理把 $n$ 质因数分解为： $n = p_{1}^{α_{1}} \times p_{2}^{α_{2}} \times \dots \times p_{k}^{α_{k}}$ ；
那么 $n$ 的约数个数为： $f (n) = \prod_{i = 1}^{k} (α_{i} + 1) = (α_{1} + 1) (α_{2} + 1) \dots (α_{k} + 1)$ 。

证明：

显然， $p_{1}^{α_{1}}$ 的约数为 $p_{1}^{0}, p_{1}^{1}, \dots, p_{1}^{k}$ ，同理： $p_{i}^{α_{i}}$ 的约数为 $p_{i}^{0}, p_{i}^{1}, \dots, p_{i}^{i}$ ；
实际上 $n$ 的约数是在 $p_{1}^{α_{1}}, p_{2}^{α_{2}}, \dots p_{k}^{α_{k}}$ 每个数的约数中分别挑一个相乘得来的，那么 $n$ 的每个约数就都可以被分解为 $d = p_{1}^{β_{1}} \times p_{2}^{β_{2}} \times \dots \times p_{k}^{β_{k}}$ （其中 $0 \leq β_{i} \leq α_{i}$ ）；
又根据算术基本定理：每一个数的质因数分解是唯一的，那么 $β_{i}$ 的所有组合就对应了 $n$ 的所有约数；
而每个 $β_{i}$ 都有 $0 \dots α_{i}$ 共 $α_{i} + 1$ 种选择，所以 $d$ 共有 $\prod_{i = 1}^{k} (α_{i} + 1)$ 个组合，那么 $n$ 也就有这么多个约数。

模板代码：

C++

// 求一个数的约数个数
int count_divisors(int n) {
    int cnt = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
           	cnt *= s + 1;
        }
    }
    if (n > 1) cnt *= 2;
    return cnt;
}

// 求一个数的约数个数
int count_divisors(int n) {
    int cnt = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
           	cnt *= s + 1;
        }
    }
    if (n > 1) cnt *= 2;
    return cnt;
}

时间复杂度：

最差： $O (\sqrt{n})$ ；
最好： $O (\log N)$ 。

一些与约数个数相关的性质

$1 \sim N$ 中所有数的约数个数之和总和约为 $N \log N$ 个；
$[0, 2 \times 10^{9}]$ 范围内的约数个数最多的数的约数约有 1600 个。

约数之和

模板题：【数学】约数之和。

原理：

根据算术基本定理把 $n$ 质因数分解为： $n = p_{1}^{α_{1}} \times p_{2}^{α_{2}} \times \dots \times p_{k}^{α_{k}}$ ；
那么 $n$ 的约数之和为：
$\begin{aligned} σ (n) & = \prod_{i = 1}^{k} (\sum_{j = 0}^{α_{k}} p_{i}^{j}) \\ = (p_{1}^{0} + p_{1}^{1} + p_{1}^{2} + \dots + p_{1}^{α_{1}}) (p_{2}^{0} + p_{2}^{1} + p_{2}^{2} + \dots + p_{2}^{α_{2}}) \dots (p_{k}^{0} + p_{k}^{1} + p_{k}^{2} + \dots + p_{k}^{α_{k}}) \end{aligned}$

证明：

显然， $p_{1}^{α_{1}}$ 的约数为 $p_{1}^{0}, p_{1}^{1}, \dots, p_{1}^{k}$ ，同理： $p_{i}^{α_{i}}$ 的约数为 $p_{i}^{0}, p_{i}^{1}, \dots, p_{i}^{i}$ ；
实际上 $n$ 的约数是在 $p_{1}^{α_{1}}, p_{2}^{α_{2}}, \dots p_{k}^{α_{k}}$ 每个数的约数中分别挑一个相乘得来的；
可知共有 $(α_{1} + 1) (α_{2} + 1) \dots (α_{k} + 1)$ 种挑法，即约数个数。
由乘法原理可知它们的和为：
$\begin{aligned} σ (n) & = \prod_{i = 1}^{k} (\sum_{j = 0}^{α_{k}} p_{i}^{j}) \\ = (p_{1}^{0} + p_{1}^{1} + p_{1}^{2} + \dots + p_{1}^{α_{1}}) (p_{2}^{0} + p_{2}^{1} + p_{2}^{2} + \dots + p_{2}^{α_{2}}) \dots (p_{k}^{0} + p_{k}^{1} + p_{k}^{2} + \dots + p_{k}^{α_{k}}) \end{aligned}$

模板代码：

C++

// 求一个数的约数之和
int sum_divisors(int n) {
    int sum = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
			int tmp = 1;
            while (n % i == 0) {
                n /= i;
                tmp = i * tmp + 1;
            }
            sum *= tmp;
        }
    }
    if (n > 1) sum *= n + 1;
    return sum;
}

// 求一个数的约数之和
int sum_divisors(int n) {
    int sum = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
			int tmp = 1;
            while (n % i == 0) {
                n /= i;
                tmp = i * tmp + 1;
            }
            sum *= tmp;
        }
    }
    if (n > 1) sum *= n + 1;
    return sum;
}

最大公约数

原理：辗转相除法（欧几里得算法）： $gcd (a, b) = gcd (b, a mod b)$ 。

证明：

已知 $a mod b = a - ⌊ \frac{a}{b} ⌋ \cdot b$ ，设 $c = ⌊ \frac{a}{b} ⌋$ ，则现在要证明 $gcd (a, b) = gcd (b, a - c \cdot b)$ ；
对于 $gcd (a, b)$ ，设 $d ∣ a, d ∣ b$ ：
- 则显然有 $d ∣ a x + b y, x, y \in Z$ ，当 $x = 1, y = c$ 时， $d ∣ a - c \cdot b$ ；
- $d ∣ b, d ∣ a - c \cdot b$ 同时成立，则有 $gcd (a, b) \subseteq gcd (b, a - c \cdot b)$ 。
对于 $gcd (b, a - c \cdot b)$ ，设 $d ∣ b, d ∣ a - c \cdot b$ ：
- 则显然有 $d ∣ a - c \cdot b + c \cdot b \Rightarrow d ∣ a$ ；
- $d ∣ a, d ∣ b$ 同时成立，则有 $gcd (b, a - c \cdot b) \subseteq gcd (a, b)$ 。
$gcd (a, b) = gcd (b, a - c \cdot b)$ 得证，同时 $gcd (a, b) = gcd (b, a mod b)$ 也成立。

模板代码：（递归实现）

Java / C++

C++

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

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

欧拉函数

公式求欧拉函数

详细介绍及原理：欧拉函数 - OI Wiki。

若在算术基本定理中： $n = p_{1}^{α_{1}} \times p_{2}^{α_{2}} \times \dots \times p_{k}^{α_{k}}$ 。

那么 $n$ 的欧拉函数： $ϕ (n) = n \times \prod_{i = 1}^{k} (1 - \frac{1}{p_{i}}) = n \times \frac{p_{1} - 1}{p_{1}} \times \frac{p_{2} - 1}{p_{2}} \times \dots \times \frac{p_{k} - 1}{p_{k}}$ 。

模板代码：

C++

typedef long long LL;

// 求一个数的欧拉函数
LL phi(int n) {
    LL res = n;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            while (n % x == 0) n /= x;
            res = res * (x - 1) / x;
        }
    }
    if (n > 1) res = res * (n - 1) / n;
    return res;
}

typedef long long LL;

// 求一个数的欧拉函数
LL phi(int n) {
    LL res = n;
    for (int x = 2; x <= n / x; ++x) {
        if (n % x == 0) {
            while (n % x == 0) n /= x;
            res = res * (x - 1) / x;
        }
    }
    if (n > 1) res = res * (n - 1) / n;
    return res;
}

时间复杂度： $O (\sqrt{N})$ 。

筛法求欧拉函数之和

求 $1 \sim n$ 中每个数的欧拉函数之和：

Java

long sumEulers(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1], phi = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; ++j) {
            isNotPrime[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    long res = 0L;
    for (int i = 1; i <= n; ++i) res += phi[i];
    return res;
}

long sumEulers(int n) {
    int cnt = 0;
    int[] primes = new int[n + 1], phi = new int[n + 1];
    boolean[] isNotPrime = new boolean[n + 1];
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; ++j) {
            isNotPrime[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    long res = 0L;
    for (int i = 1; i <= n; ++i) res += phi[i];
    return res;
}

时间复杂度： $O (N)$ 。

快速幂

详细介绍及原理：快速幂 - OI Wiki。

模板代码：

JavaC++

Java

long kasumi(long base, long exp, long mod) {
    long res = 1L;
    while (exp != 0) {
        if ((exp & 1) != 0) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

long kasumi(long base, long exp, long mod) {
    long res = 1L;
    while (exp != 0) {
        if ((exp & 1) != 0) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

C++

typedef long long LL;

LL kasumi(LL base, LL exp, LL mod) {
    LL res = 1LL;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

typedef long long LL;

LL kasumi(LL base, LL exp, LL mod) {
    LL res = 1LL;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

慢速乘

防止乘数及模数很大但还在 long long 范围内时直接做乘爆 long long 的问题。

JavaC++

Java

long slowMul(long a, long b, long m) {
    long c = 0L;
    while (b > 0) {
        if ((b & 1) != 0) c = (c + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return c;
}

long slowMul(long a, long b, long m) {
    long c = 0L;
    while (b > 0) {
        if ((b & 1) != 0) c = (c + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return c;
}

C++

typedef long long LL;

LL slow_mul(LL a, LL b, LL m) {
    LL c = 0LL;
    while (b) {
        if (b & 1) c = (c + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return c;
}

typedef long long LL;

LL slow_mul(LL a, LL b, LL m) {
    LL c = 0LL;
    while (b) {
        if (b & 1) c = (c + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return c;
}

扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求 $a x + b y = gcd (a, b)$ （裴蜀定理）的一组可行解。

过程

设：

$a x_{1} + b y_{1} = gcd (a, b)$

$b x_{2} + (a mod b) y_{2} = gcd (b, a mod b)$

由欧几里得算法可知： $gcd (a, b) = gcd (b, a mod b)$

所以：

\begin{aligned} a x_{1} + b y_{1} & = b x_{2} + (a mod b) y_{2} \\ a x_{1} + b y_{1} & = b x_{2} + (a - ⌊ \frac{a}{b} ⌋ \cdot b) y_{2} \\ a x_{1} + b y_{1} & = b x_{2} + a y_{2} - b ⌊ \frac{a}{b} ⌋ y_{2} \\ a x_{1} + b y_{1} & = a y_{2} + b (x_{2} - ⌊ \frac{a}{b} ⌋ y_{2}) \end{aligned}

因为 $a = a, b = b$ ，所以： ${\begin{cases} x_{1} = y_{2} \\ y_{1} = x_{2} - ⌊ \frac{a}{b} ⌋ y_{2} \end{cases}$ 。

将 $x_{2}, y_{2}$ 不断代入递归求解，直至 $b = 0$ 时： $a x + 0 y = a$ ，显然 ${\begin{cases} x = 1 \\ y = 0 \end{cases}$ 是一组解，此时退出递归。

模板代码

Java

int x, y;
    
int exgcd(int a, int b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

int x, y;
    
int exgcd(int a, int b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

线性同余方程

定义

形如：

a x \equiv b (\mod n)

的方程称为 线性同余方程（Congruence Equation）。其中， $a, b, n$ 为给定整数， $x$ 为未知数，需要从区间 $[0, n - 1]$ 中求解，当解不唯一时需要求出全体解。

用扩展欧几里得算法求解

根据以下两个定理，可以求出线性同余方程 $a x \equiv b (\mod n)$ 的解。

定理 1

$a x \equiv b (\mod n)$ 可以改写为 $a x = n y^{'} + b$ ，移项得 $a x - n y^{'} = b$ 。设 $y = - y^{'}$ ，则有 $a x + n y = b$ 。其中 $x$ 和 $y$ 是未知数。这两个方程是等价的，有整数解的充要条件为 $gcd (a, n) ∣ b$ （因为 $a x + n y$ 一定要是 $g c d (a, n)$ 的倍数）。

很容易发现，经过转换后的方程很像裴蜀定理的结论（ $a x + b y = gcd (a, b)$ ），于是我们可以先用扩展欧几里得算法求出一组 $x_{0}^{'}, y_{0}^{'}$ ，也就是 $a x_{0}^{'} + n y_{0}^{'} = gcd (a, n)$ ，然后两边同时除以 $gcd (a, n)$ ，再乘 $b$ 。就得到了方程：

a \cdot \frac{b}{gcd (a, n)} \cdot x_{0}^{'} + n \cdot \frac{b}{gcd (a, n)} \cdot y_{0}^{'} = b

于是找到方程的一个解：

{\begin{cases} x_{0} = \frac{b}{gcd (a, n)} \cdot x_{0}^{'} \\ y_{0} = \frac{b}{gcd (a, n)} \cdot y_{0}^{'} \end{cases}

定理 2

若 $gcd (a, n) = 1$ ，且 $x_{0}, y_{0}$ 为方程 $a x + n y = b$ 的一组解，设 $t = \frac{n}{gcd (a, n)}$ ，则该方程的任意解可表示为：

{\begin{cases} x = x_{0} + n t \\ y = y_{0} - a t \end{cases}

并且对任意整数 $t$ 都成立。

根据定理 2，可以从已求出的一个解，求出方程的所有解。实际问题中，往往要求出一个最小整数解，也就是一个特解（例如使用扩展欧几里得算法求解乘法逆元）：

x_{min} = (x_{0} mod t + t) mod t

因为 $gcd (a, n) = 1$ ，所以 $t = \frac{n}{gcd (a, n)} = n$ ，于是就有：

x_{min} = (x_{0} mod n + n) mod n

模板题：

模板代码

Java

int x, y;

int exgcd(int a, int b) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

// ax === b (mod n) 的解
int solve(int a, int b, int n) {
    int d = exgcd(a, n);
    if (b % d != 0) return -1; // 不存在整数解
    else return (int) (1L * x * (b / d) % n);
}

int x, y;

int exgcd(int a, int b) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

// ax === b (mod n) 的解
int solve(int a, int b, int n) {
    int d = exgcd(a, n);
    if (b % d != 0) return -1; // 不存在整数解
    else return (int) (1L * x * (b / d) % n);
}

乘法逆元(模逆元)

定义

若整数 $b, p$ 互质^[1]，且对于任意一个整数 $a$ ，如果满足 $b ∣ a$ ^[2] ，则存在一个整数 $x$ ，使得 $\frac{a}{b} \equiv a \cdot x (\mod p)$ ^[3] 。称 $x$ 为 $b$ 在模 $p$ 意义下的乘法逆元，记作 $b^{- 1} (\mod p)$ 。

作用

在要除以一个数，再取模时，把除法变成乘法运算，然后再取模。

快速幂求逆元

只能在模数为质数的情况下使用。

根据逆元的定义，有： $\frac{a}{b} \equiv a \cdot b^{- 1} (\mod p)$ ；

两边同乘 $b$ 得： $a \equiv a \cdot b \cdot b^{- 1} (\mod p)$ ；

所以： $b \cdot b^{- 1} \equiv 1 (\mod p)$ ①；

根据费马小定理：若 $p$ 为质数且 $b, p$ 互质，则 $b^{p - 1} \equiv 1 (\mod p)$ 。

从上式 $b^{p - 1}$ 中拆出一个 $b$ 得到： $b \cdot b^{p - 2} \equiv 1 (\mod p)$ 。

结合①式得到： $b^{- 1} \equiv b^{p - 2} (\mod p)$ 。

综上，在 $b$ 存在乘法逆元的条件下，求出 $b^{p - 2} mod p$ 即为 $b$ 在模 $p$ 意义下的乘法逆元。

$b^{p - 2}$ 使用快速幂求解。

扩展欧几里得算法求逆元

根据逆元的定义，有： $\frac{a}{b} \equiv a \cdot b^{- 1} (\mod p)$ ；

两边同乘 $b$ 得： $a \equiv a \cdot b \cdot b^{- 1} (\mod p)$ ；

所以： $b \cdot b^{- 1} \equiv 1 (\mod p)$ ；

设 $a = b, x = b^{- 1}, n = p$ ，上式表达为： $a x \equiv 1 (\mod n)$ ，需要求解式中的 $x$ ，其实就是求解线性同余方程 $a x \equiv b (\mod n)$ 在 $b = 1$ 的特殊情况下的解。根据逆元的定义有： $gcd (a, n) = 1$ ，参考求解线性同余方程 - 用扩展欧几里得算法求解 - 定理 2， $x$ 的一个最小整数解为：

x = (x mod n + n) mod n

模板代码：

Java

int x, y;

int exgcd(int a, int b) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

// a在模n意义下的逆元
int inv(int a, int n) {
    exgcd(a, n);
    return (x % n + n) % n;
}

int x, y;

int exgcd(int a, int b) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

// a在模n意义下的逆元
int inv(int a, int n) {
    exgcd(a, n);
    return (x % n + n) % n;
}

组合数

从 $n$ 个不同元素中，任取 $m (m \leq n)$ 个元素组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m (m \leq n)$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数。用符号 $C_{n}^{m}$ 来表示，组合数也常用 $(\binom{n}{m})$ 表示，读作「 $n$ 选 $m$ 」，即 $C_{n}^{m} = (\binom{n}{m})$ 。

组合数计算公式：

C_{n}^{m} = \frac{n!}{m! (n - m)!}

特别地，规定当 $m > n$ 时， $A_{n}^{m} = C_{n}^{m} = 0$ 。

递推求组合数

模板题：求组合数 I。

原理： $C_{n}^{m} = C_{n - 1}^{m} + C_{n - 1}^{m - 1}$ 。

证明：

在 $n$ 个物品中选择 $m$ 个物品（ $C_{n}^{m}$ ），假如当前拿出来了一个物品：

如果该物品不在要选择的 $m$ 个物品中，那么我们还需要在 $n - 1$ 个物品中选择 $m$ 个物品（ $C_{n - 1}^{m}$ ）；
如果该物品在要选择的 $m$ 个物品中，那么我们还需要在 $n - 1$ 个物品中选择 $m - 1$ 个物品（ $C_{n - 1}^{m - 1}$ ）。

综上， $C_{n}^{m} = C_{n - 1}^{m} + C_{n - 1}^{m - 1}$ 成立。

适用数据范围： $1 \leq T \leq 10000, 1 \leq m \leq n \leq 2000$ 。

模板代码：

Java

static final int N;
static int[][] c = new int[N][N];

static void comb() {
    for (int n = 0; n < N; ++n) {
        for (int m = 0; m <= n; ++m) {
			if (m == 0) c[n][m] = 1;
            else c[n][m] = c[n - 1][m] + c[n - 1][m - 1];
        }
    }
}

// ans: c[a][b]

static final int N;
static int[][] c = new int[N][N];

static void comb() {
    for (int n = 0; n < N; ++n) {
        for (int m = 0; m <= n; ++m) {
			if (m == 0) c[n][m] = 1;
            else c[n][m] = c[n - 1][m] + c[n - 1][m - 1];
        }
    }
}

// ans: c[a][b]

预处理阶乘求组合数

模板题：求组合数 II。

原理： $C_{n}^{m} = n! \times (m!)^{- 1} \times (n! - m!)^{- 1} (\mod 10^{9})$ （逆元的简单应用）。

适用数据范围： $1 \leq T \leq 10000, 1 \leq m \leq n \leq 10^{5}$ 。

模板代码：

Java

// MOD必须是质数才能用快速幂求逆元
static final int N, MOD;
// fact[i]表示i的阶乘(% MOD)  infact[i]表示i的阶乘的逆元(% MOD)
static int[] fact = new int[N], infact = new int[N];

// 预处理1~N的阶乘及其逆元
static {
    fact[0] = 1;
    for (int i = 1; i < N; ++i) {
        fact[i] = (int) (1L * fact[i - 1] * i % MOD);
        infact[i] = (int) qmi(fact[i], MOD - 2, MOD);
    }
}

// 快速幂 用作求逆元
static long qmi(long base, long exp, long mod) {
    long res = 1L;
    while (exp > 0) {
        if ((exp & 1) == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

static int C(int n, int m) {
    return n == m ? 1 : (int) (1L * fact[n] * infact[m] % MOD * infact[n - m] % MOD);
}

// ans: C(a, b)

// MOD必须是质数才能用快速幂求逆元
static final int N, MOD;
// fact[i]表示i的阶乘(% MOD)  infact[i]表示i的阶乘的逆元(% MOD)
static int[] fact = new int[N], infact = new int[N];

// 预处理1~N的阶乘及其逆元
static {
    fact[0] = 1;
    for (int i = 1; i < N; ++i) {
        fact[i] = (int) (1L * fact[i - 1] * i % MOD);
        infact[i] = (int) qmi(fact[i], MOD - 2, MOD);
    }
}

// 快速幂 用作求逆元
static long qmi(long base, long exp, long mod) {
    long res = 1L;
    while (exp > 0) {
        if ((exp & 1) == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

static int C(int n, int m) {
    return n == m ? 1 : (int) (1L * fact[n] * infact[m] % MOD * infact[n - m] % MOD);
}

// ans: C(a, b)

卢卡斯定理求组合数

模板题：求组合数 III。

原理：

若 $a < p & b < p$ ，那么直接从定义出发，使用公式求解：

C_{n}^{m} = \frac{n!}{m! (n - m)!} = \frac{\prod_{i = n - m + 1}^{n} i}{m!} = \frac{n (n - 1) \dots (n - m + 2) (n - m + 1)}{1 \times 2 \times \dots \times m}

否则代入 Lucas 公式： $C_{n}^{m} mod p = C_{n mod p}^{m mod p} \cdot C_{⌊ n / p ⌋}^{⌊ m / p ⌋} mod p$ 递归计算。

适用数据范围： $1 \leq T \leq 20, 1 \leq m \leq n \leq 10^{18}, 1 \leq p \leq 10^{5}$ 。

模板代码：

Java

// 快速幂 用作且求逆元
static long qmi(long base, long exp, long mod) {
    long res = 1L;
    while (exp > 0) {
        if ((exp & 1) == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

// 求组合数
static long C(long n, long m, long p) {
    long nume = 1L, deno = 1L;
    for (long a = n, b = 1; b <= m; --a, ++b) {
        nume = nume * a % p;
        deno = deno * b % p;
    }
    return nume * qmi(deno, p - 2, p) % p;
}

// 卢卡斯定理
static long lucas(long n, long m, long p) {
    if (n < p && m < p) return C(n, m, p);
    else return lucas(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}

// ans: lucas(a, b, p)

// 快速幂 用作且求逆元
static long qmi(long base, long exp, long mod) {
    long res = 1L;
    while (exp > 0) {
        if ((exp & 1) == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

// 求组合数
static long C(long n, long m, long p) {
    long nume = 1L, deno = 1L;
    for (long a = n, b = 1; b <= m; --a, ++b) {
        nume = nume * a % p;
        deno = deno * b % p;
    }
    return nume * qmi(deno, p - 2, p) % p;
}

// 卢卡斯定理
static long lucas(long n, long m, long p) {
    if (n < p && m < p) return C(n, m, p);
    else return lucas(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}

// ans: lucas(a, b, p)

高精度+质因数分解求组合数

模板题：求组合数 IV。

原理：

根据公式： $C_{n}^{m} = \frac{n!}{m! (n - m)!}$ ，分别把 $n!, m!, (n - m)!$ 质因数分解，对于 $1 \sim N$ 中的每个质数，维护 $m p [i]$ 表示： $n!$ 质因数分解后 $i$ 的次数 $-$ $m!$ 质因数分解后 $i$ 的次数 $-$ $(n - m)!$ 质因数分解后 $i$ 的次数。最后把 $m p$ 中有次数的质数按照其次数乘起来就能得到答案；
快速计算 $n$ 的阶乘的质因数分解中质因子 $x$ 的数量：勒让德定理；
高精度 Java 用 BigInteger 包。

适用数据范围： $1 \leq m \leq n \leq 5000$ 。

Java

// 预处理筛出1~N之间的所有质数
static final int N;
static int[] primes = new int[N];
static int cnt = 0;
static boolean[] np = new boolean[N + 1];
// 线性筛
static {
    for (int x = 2; x <= N; ++x) {
        if (!np[x]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= N / x; ++i) {
            np[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
}

// 求n!中因子p的数量
static int count(int n, int d) {
    int cnt = 0;
    while (n > 0) cnt += n /= d;
    return cnt;
}

static BigInteger C(int n, int m) {
    BigInteger res = BigInteger.valueOf(1);
    for (int i = 0; i < cnt; ++i) {
        int p = primes[i];
        // 求每个质因子的幂次数
        int cnt = count(n, p) - count(m, p) - count(n - m, p);
        BigInteger bp = BigInteger.valueOf(p);
        while (cnt-- > 0) res = res.multiply(bp);
    }
    return res;
}

// ans: C(a, b)

// 预处理筛出1~N之间的所有质数
static final int N;
static int[] primes = new int[N];
static int cnt = 0;
static boolean[] np = new boolean[N + 1];
// 线性筛
static {
    for (int x = 2; x <= N; ++x) {
        if (!np[x]) primes[cnt++] = x;
        for (int i = 0; primes[i] <= N / x; ++i) {
            np[primes[i] * x] = true;
            if (x % primes[i] == 0) break;
        }
    }
}

// 求n!中因子p的数量
static int count(int n, int d) {
    int cnt = 0;
    while (n > 0) cnt += n /= d;
    return cnt;
}

static BigInteger C(int n, int m) {
    BigInteger res = BigInteger.valueOf(1);
    for (int i = 0; i < cnt; ++i) {
        int p = primes[i];
        // 求每个质因子的幂次数
        int cnt = count(n, p) - count(m, p) - count(n - m, p);
        BigInteger bp = BigInteger.valueOf(p);
        while (cnt-- > 0) res = res.multiply(bp);
    }
    return res;
}

// ans: C(a, b)

卡特兰数

模板题：满足条件的01序列。

C_{2 n}^{n} - C_{2 n}^{n - 1} = \frac{C_{2 n}^{n}}{n + 1}

$gcd (b, m) = 1$ 。 ↩︎
$a$ 能被 $b$ 整除（ $\frac{a}{b}$ 是一个整数）。 ↩︎
$\frac{a}{b}$ 在模 $p$ 同余于 $a \cdot x$ （ $\frac{a}{b} mod p = a \cdot x mod p$ ）。 ↩︎

数学 ​

向上取整 ​

加法原理 ​

乘法原理 ​

算术基本定理 ​

裴蜀定理 ​

平方和公式 ​

质数 ​

试除法判质数 ​

试除法分解质因数 ​

筛质数 ​

朴素筛 ​

埃氏筛 ​

线性筛（欧拉筛） ​

勒让德定理 ​

约数 ​

试除法求所有约数 ​

约数个数 ​

求约数个数 ​

一些与约数个数相关的性质 ​

约数之和 ​

最大公约数 ​

欧拉函数 ​

公式求欧拉函数 ​

筛法求欧拉函数之和 ​

快速幂 ​

慢速乘 ​

扩展欧几里得算法 ​

过程 ​

模板代码 ​

线性同余方程 ​

定义 ​

用扩展欧几里得算法求解 ​

定理 1 ​

定理 2 ​

模板代码 ​

乘法逆元(模逆元) ​

定义 ​

作用 ​

快速幂求逆元 ​

扩展欧几里得算法求逆元 ​

组合数 ​

递推求组合数 ​

预处理阶乘求组合数 ​

卢卡斯定理求组合数 ​

高精度+质因数分解求组合数 ​

卡特兰数 ​

数学

向上取整

加法原理

乘法原理

算术基本定理

裴蜀定理

平方和公式

质数

试除法判质数

试除法分解质因数

筛质数

朴素筛

埃氏筛

线性筛（欧拉筛）

勒让德定理

约数

试除法求所有约数

约数个数

求约数个数

一些与约数个数相关的性质

约数之和

最大公约数

欧拉函数

公式求欧拉函数

筛法求欧拉函数之和

快速幂

慢速乘

扩展欧几里得算法

过程

模板代码

线性同余方程

定义

用扩展欧几里得算法求解

定理 1

定理 2

模板代码

乘法逆元(模逆元)

定义

作用

快速幂求逆元

扩展欧几里得算法求逆元

组合数

递推求组合数

预处理阶乘求组合数

卢卡斯定理求组合数

高精度+质因数分解求组合数

卡特兰数