【数学】数学杂烩

前言

众所周知，数论是 OI 中很重要的一部分。

然而作为一个即将初赛的 $CSP-S$ 选手，我基本不会数论。

于是现在我要开始学数论！！！

---

数论

数论是纯粹数学的分支之一，主要研究整数的性质。

在学习数论之前，先来了解一下一些基本知识

---

模运算

模运算的定义十分简单，即余数。

具体来讲，对于两个非负整数 $a$ , $b$，$a/b$ 的余数记做 $amodb$，即 $a$ 模 $b$。

在这里，$mod$ 相当于 C++ 中的 $\mathrm{\%}$ 运算。

而对于非负整数 $a$ 与负整数 $b$ , $amodb$ 的值即为 $a$ 除以 $b$ 的余数再加上 $b$。

---

同余

若 $amodc=bmodc$, 则称 $a$ 与 $b$ 在模 $c$ 意义下同余，写作 $a\equiv b(\mathrm{mod}c)$

---

模运算的性质

对于整数 $a$ 与正整数 $b$，有：

$$a+b\equiv (amodp)+(bmodp)(\mathrm{mod}p)$$$$a-b\equiv (amodp)-(bmodp)(\mathrm{mod}p)$$$$a\times b\equiv (amodp)\times (amodp)(\mathrm{mod}p)$$

我们将这种性质称为模运算对加法，减法，乘法封闭。

但要注意，除法并不满足这种性质，因此，我们一般很少直接使用除法。

---

乘法逆元

对于两个互质 (注意，必须要互质) 的非负整数 $a$，$p$ , 存在 $ax(\mathrm{mod}p)=1$。

称 $x$ 是 $a$ 在模 $p$ 意义下的乘法逆元，记做 $a^{-1}$。

不难看出，乘法逆元具有以下性质：

$$x\times x^{-1}\equiv 1(\mathrm{mod}p)$$

乘法逆元的可以用于代替计算除法，在模意义下，除以一个数等价于乘其乘法逆元。

---

费马小定理

对于任意的正整数 $a$ 和质数 $p$(需保证 $a$ 不是 $p$ 的倍数)，有

$$a^{p-1}\equiv 1(\mathrm{mod}p)$$

将上面的公式变一下形，就成了

$$a\times a^{p-2}\equiv 1(\mathrm{mod}p)$$

即 $a\equiv \frac{1}{a^{p-2}}(\mathrm{mod}p)$

根据乘法逆元的定义，$a^{p-2}$ 即为 $a$ 在模 $p$ 意义下的乘法逆元。

对此，我们可以用快速幂进行计算，时间复杂度为 $O(\log a)$

Code:

#define ll long long
#define HA 19260817  //这里的HA为模数.

ll Pow(ll a , ll n){
    if(n == 0){
        return 1;
    }
    if(n == 1){
        return a;
    }
    ll c = Pow(a , n >> 1) % HA;
    if(n % 2 == 0){
        return ((c % HA) * (c % HA)) % HA;
    }
    else{
        return ((c % HA) * (c % HA) * (a % HA)) % HA;
    }
}

ll inv(ll num){
    return Pow(a , HA - 2);
}

但要注意，费马小定理只有在模数为质数时才可以使用，因为如果模数不是质数，并不是每一个数都存在逆元。

---

线性递推

如果要求一个数的乘法逆元，我们可以用费马小定理很快求出。

但如果要在模数很大的情况下求 $n$ 个数的逆元的话，费马小定理的时间复杂度就成了 $O(n\times p)$。

因为 $p$ 一般都为一个 ${10}^9$ 级别的质数，因此，费马小定理很难在规定时间内求出答案。

这时，我们将需要使用线性递推法。

线性递推法可以在线性的时间内求出从 $2$ 到 $p$ 的所有数的逆元，其推导过程如下：

首先，$1^{-1}\equiv 1(\mathrm{mod}p)$。这是很显然的。

然后设 $p=k\times i+r$，即 $k$ 为 $p/i$ 的商，$r$ 为余数

将这个式子放在模 $p$ 意义下，可得：$k\times i+r\equiv 0(\mathrm{mod}p)$

然后乘上 $i^{-1},r^{-1}$，可得：$k\times r^{-1}+i^{-1}\equiv 0(\mathrm{mod}p)$

$$i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor \times (pmodi{)}^{-1}(\mathrm{mod}p)$$

Code

#define N 3000001

int inv[N] , n;

inv[1] = 1;
for(int i = 2; i <= n; i ++){
    inv[i] = (HA - HA / i) * inv[HA % i] % HA;
}

时间复杂度为 $O(n)$，很适合用来预处理从 $1$ 到 $n$ 所有数的逆元。

---

Gcd & Lcm

最大公因数 (Gcd)

能够同时整除 $a$ 与 $b$ 的最大的数，叫做 $a$ 与 $b$ 的最大公因数，记做 $gcd(a,b)$

对于任意的 $gcd(a,b)$，有$gcd(a,b)=gcd(a,a-b)=gcd(b,a-b)$

---

欧几里得算法

一般情况下，我们使用欧几里得算法求解两个数的最大公因数。

刚刚提到，对于任意的 $gcd(a,b)$，有$gcd(a,b)=gcd(a,a-b)=gcd(b,a-b)$

考虑 $a$ 远远大于 $b$ 时，则

$$gcd(a,b)=gcd(b,a-b)=gcd(b,a-b-b)=gcd(b,a-b-b-b)\dots \dots =gcd(b,amodb)$$

Code:

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

时间复杂度取决于其递归深度，为 $O(\log a)$

---

最小公倍数 (Lcm)

同时是整数 $a$ 与整数 $b$ 的倍数的最小的数叫做 $a$ 与 $b$ 的最小公倍数，记做 $lcm(a,b)$

直接套用公式即可求出。

$$lcm(a,b)=\frac{a\times b}{gcd(a,b)}$$

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

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

时间复杂度同样也是 $O(\log a)$ 的。

---

线性同余方程

关于 $x$ 的形如$ax\equiv b(\mathrm{mod}p)$的方程称为线性同余方程。

求解以上的线性同余方程，相当于求解下面的不定方程

$$ax+by=p$$

---

扩展欧几里得 (Exgcd)

扩展欧几里得算法 exgcd 可以在求出 $gcd(a,b)$ 的同时求出 $ax\equiv b(\mathrm{mod}gcd(a,b))$，即二元一次不定方程 $ax+by=gcd(a,b)$ 的一组整数解。

其原理在于收集欧几里得算法在求解 $gcd(a,b)$ 时产生的式子并带入。

举个栗子 (就不给你吃 o (´^｀) o)：

在求 $gcd(71,13)$ 时，可以得到以下式子

$$71=13\times 5+6$$$$13=6\times 2+1$$

现在移一下项，把余数都移到左边，就成了下面这个样子

$$6=71+13\times (-5)$$$$1=13+6\times (-2)$$

从 $gcd(71,13)$ 开始，把刚刚推出的式子一一带入，就成了下面的样子

$gcd(71,13)$
$=1$
$=13+6\times (-2)$
$=13+[71+13\times (-5)]\times (-2)$
$=13\times 11+71\times (-2)$
$=71\times (-2)+13\times 11$

看最后一个式子，是不是就是 $a=71$ ,$b=13$ 时的不定方程？

所以解为 $x=-2$, $y=11$。

在刚刚的过程中，不难看出每一次计算都交换了 $x$ 与 $y$ 的位置，并将 $y$ 减去了原来与 $x$ 辗转相除的商的乘积。

Code:

#define ll long long

ll x , y;

void exgcd(ll a , ll b){
    if(b == 0){
        x = 1;
        y = 0;
        return ;
    }
    exgcd(b , a % b);
    ll tx = x;
    x = y;
    y = tx - a / b * y;
}

---

素数

素数，即质数，指只有 $1$ 与它本身两个因子的数。

素数判定

如何判定一个数 $n$ 是不是质数呐？？？

最朴素的办法应该就是把 $2$ 到 $n-1$ 的数都试除一遍，看能否除尽。

但我们发现并不需要除到 $n-1$，只需要除到 $\sqrt{n}$ 即可。

Code:

bool Prime(int n){
    for(int i = 2; i * i <= n; i ++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

时间复杂度为 $O(\sqrt{n})$，对于单个数据而言，已经很优秀了。

---

素数筛法

但大多数时候，我们不仅要判断单个数是否为质数，而是要判断含有 $n$ 个数的区间内有多少素数或有哪些素数。

这时，跑 $n$ 边朴素算法的时间复杂度高达 $O(n\sqrt{num})$，已经远远无法满足我们的要求。

因此，我们需要更加高效的做法。

---

埃拉托斯特尼筛（埃氏筛）

埃氏筛的核心思想只有一句话：素数的倍数一定不是素数

因此，我们可以默认数组中的每一个数都为素数，然后依次筛掉。

特别提醒：$1$ 既不是质数也不是合数，因此，需要从 $2$ 开始筛

Code:

bool Prime[N];

void IS_Prime(int n){
    for(int i = 2; i <= n; i ++){
        Prime[i] = true;
    }
    for(int i = 2; i * i <= n; i ++){
        if(Prime[i]){
            for(int j = 2 * i; j < n; j += i){
                Prime[j] = false;
            }
        }
    }
    return ;
}

时间复杂度为 $O(n\log \log n)$，属于比较优秀的筛法。

---

欧拉筛

不难看出，刚刚的埃氏筛中有一个致命的缺点：一个数可能会被筛掉多次。

因此，我们可以对此作出改善。

Code：

int a[N]; 
bool Prime[N];
int num = 0;

void IS_Prime(int n){
    for(int i = 2; i <= n; i ++){
        Prime[i] = true;
    }
    for(int i = 2; i * i <= n; i ++){
        if(Prime[i]){
            a[num ++] = i;
        }
        for(int j = 1; j <= num && i * a[j] < n; j ++){
            Prime[i * a[j]] = false;
            if(!(i % a[j])){
                break;
            }
        }
    }
    return ;
}

现在，我们可以保证每个数据被其最小质因子筛掉，因此，时间复杂度为 $O(n)$。

---

数论分块

数论分块是一种比较特殊的分块算法，可以用来解决形如 $f(n)=\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor$ 的问题

显然，这个式子直接求解的复杂度为 $O(n)$。但面对形如 ${10}^{12}$ 的大数据时，则显得比较无能为力。

这时候，我们就需要一个更加优秀的做法。

观察一下这个式子，并手造几组小数据带入，可以得到下表

$n$	分步计算	$f(n)$
1	1	1
2	2 + 1	3
3	3 + 1 + 1	5
4	4 + 2 + 1 + 1	8
5	5 + 2 + 1 + 1 + 1	10
6	6 + 3 + 2 + 1 + 1 + 1	14
7	7 + 3 + 2 + 1 + 1 + 1 + 1	16
8	8 + 4 + 2 + 2 + 1 + 1 + 1 + 1	20
9	9 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 1	23

不难发现，对于单一的 $\lfloor \frac{n}{i}\rfloor$，有些位置的值是相同的，而且呈块状分布

继续观察，可以发现若一个块的左端点为 $l$，则其右端点为 $\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor$

直接分块求解即可。

时间复杂度为 $O(\sqrt{n})$，足以跑过 ${10}^{12}$ 的大数据。

Code：

for(int l = 1; r; l <= n; l = r + 1){
    r = n / (n / l);
    ans += n / i * (r - l + 1);
}

---

组合数学

组合数学是研究组合模型，计数，构造等方面问题的数学分治，是 $OI$ 重要的组成部分。

在学习组合数学之前，先来看一下组合数学的基本计数原理。

---

计数原理

加法原理

一般的，如果做一件事有 $n$ 种不同的途径，其中做第 $i$ 件事有 $n_i$ 种方案，则做这件事一共有 $\sum n_i$ 种方案

---

乘法原理

一般的，如果做一件事有 $n$ 个步骤，其中第 $i$ 个步骤有 $n_i$ 种不同的完成方案，则做这件事一共有 $\prod m_i$ 种方法。

---

容斥原理

统计多个集合的并集的方法如下：

1. 先把所有集合的元素加起来
2. 然后减去【多加的】每两个集合相交的元素数量
3. 然后加上【多减的】每三个集合相交的元数数量
4. ………………………………

举个栗子 (就不给你吃 o (´^｀) o)：

现在有三个集合 $A,B,C$，其中

$$A=\{0,1,2,3,4\}$$$$B=\{0,3,4,5,6\}$$$$C=\{0,5,6,7,8\}$$

请求出集合 $A,B,C$ 的并集中的元素数量。

首先，把三个集合的元素总数加起来，为 $15$。

之后减去每两个集合的交集，可得 $15-(3+3+1)=8$

之后再加上三个集合的交集，可得 $8+1=9$

显然，原集合的并集大小为 $9$。

现在把刚刚运算过程中的式子重新整理，可以得到

$$9=15-(3+3+1)+1$$

不难看出，此时等式的左边是多个集合的并的元数数量，等式的右边的每一项是几个集合的交的元素数量，右边每一项的符号取决于其项数的奇偶。

---

排列组合

全排列

将 $n$ 个不同元素按照不同的顺序进行排列，设总方案数为 $f(n)$(定义 $f(0)=1$)，考虑第一个元素的位置，则有

$$f(n)=f(n-1)\times n$$

化简一下，则 $f(n)=n!$。

---

普通排列

从 $n$ 个元素中取出 $k$ 个进行排列，设总方案数为 $P(n,k)$ 考虑每一次取数时的选择，第一次有 $n$ 种选择，第二次有 $n-1$ 种…… 第 $n$ 次则有 $n-k+1$ 种。

即$P(n,k)=\prod _{i=0}^{k-1}(n-i)$

把这个公式和 $n!$ 对比，很容易可以发现少了 $n-k$ 之后的项。

即$P(n,k)=\frac{n!}{(n-k)!}$

---

组合

从 $n$ 个元素中选取 $k$ 个元素进行组合，设总方案为 $C_n^k$。把排列数 $P(n,k)$ 等价于从 $n$ 个元素中选取 $k$ 个进行全排列。

即$P(n,k)=C_n^k\times k!$

移一下项，可得$C_n^k=\frac{P(n,k)}{k!}=\frac{n!}{(n-1)!\times k!}$

---

特殊性质

$$C_n^0=C_n^n=1$$$$C_n^1=n$$$$C_n^k=C_{n-1}^k\times C_{n-1}^{k-1}$$

其中，最后一个为 Pascal 公式，可以用来打组合数表。

---

组合数的计算

组合数表

使用 Pascal 公式递推，如果数据太大的话需要高精或者取模。

#define ll long long
#define N 1001

ll c[N][N];         //c[i][j]表示在i个数中选n个数的组合数
void get_num(int n){
    c[0][0] = 1;
    for(int i = 1; i <= n; i ++){
        c[i][0] = 1;
        for(int j = 1; j <= i; j ++){
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
}

---

单独计算

直接套公式即可

#define ll long long

ll C(int n , int k){
    ll ans = 1;
    for(int i = 1; i <= k; i ++){
        ans = ans * (n - i + 1) / i;
    }
    return ans;
}

---

参考资料

1. Menci’s Blog & 课件
2. Struct 瓶子’s Blog
3. Passer’s CSDN Blog
4. Luogu P3811【模板】乘法逆元 - 题解
5. zip-shadow’s CSDN Blog

感谢上述 dalao 对我数论学习的帮助

---

THE END