前言

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

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

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


数论

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

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


模运算

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

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

在这里,$mod$相当于C++中的$\%$运算。

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


同余

若$a \bmod c = b \bmod c$, 则称$a$与$b$在模$c$意义下同余,写作$a \equiv b\pmod c$


模运算的性质

对于整数$a$与正整数$b$,有:

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

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


乘法逆元

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

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

不难看出,乘法逆元具有以下性质:

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


费马小定理

对于任意的正整数$a$和质数$p$(需保证$a$不是$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 \pmod p$。这是很显然的。

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

将这个式子放在模$p$意义下,可得:

然后乘上$i^{-1} , r^{-1}$,可得:

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)$,有

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

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)$

直接套用公式即可求出。

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$的形如的方程称为线性同余方程。

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


扩展欧几里得(Exgcd)

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

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

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

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

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

从$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\limits_{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 , B , C$的并集中的元素数量。

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

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

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

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

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

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


排列组合

全排列

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

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


普通排列

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

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


组合

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

移一下项,可得


特殊性质

其中,最后一个为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