前言

众所周知，数论是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