数论研究的是整数的性质，是数学中最古老，最易懂也最艰深的一个学科。竞赛中经常需要进行一些运算和统计，数论知识能够帮助我们正确地运算出结果。

由于在NOIP初赛之前没有几堂课了，我们将加快进度讲解题目中最常见的一些算法，熟练掌握应对常见题目所需的数论知识并查漏补缺，对于相对冷门的算法就不做进一步展开了。

数论

符号介绍

$b\mid a$表示$b$整除$a$，$a$被$b$整除，或者说$a$是$b$的倍数。

$a\% M$以及$a\mod M$表示，带余数除法中$a$除以$M$的余数。

$a \equiv b \mod M$表示$a,b$模$M$的余数相同，或者说$a,b$关于$M$同余。

欧几里得算法

欧几里得算法是最为古老的算法，用来求解最大公约数，算法代码如下：

1
2
3

int gcd(int x, int y) {
  return y ? gcd(y, x % y) : x;
}

这里主要利用了性质 $\gcd(x,y)=\gcd(x, y \% x)$，取模操作可以进行变形$x\%y=x-\lfloor x/y\rfloor \cdot y$

上述结论可以由$\gcd(x,y)=\gcd(x,x-y)$，追根溯源会发现只要证明$\gcd(x,y)=\gcd(x,x+y)$即可，而这个命题比较容易证明。

素数判断与分解质因数

由于做法类似，将这两个问题一并讨论。

判断一个数$x$是否为素数，最简单的可以枚举$2,\cdots,x-1$，更好的方法是直接枚举$2,\cdots,\sqrt{x}$，因为一个合数最小的素因数小于等于$\sqrt{x}$，否则因为合数有至少两个素因数会推出素因数乘积大于$x$的矛盾。

需要注意$1$不是素数的特殊情况，这是最容易疏忽的地方，代码如下：

bool is_prime(int x) {
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) return false;
  }
  return x > 1;
}

若要将$x$分解素因数，可以枚举$\sqrt{x}$内的所有整数，不断从$x$中消去即可，消去留下的数若不是$1$也需要加入到素因数中，容易忘记把留下的数加入素因数。

这个过程中，一定是素数被消去，因为枚举一个合数之前一定已经枚举过它的素因数，会被它们消去。

这么做是正确的，因为一个合数至多只有一个大于$\sqrt{x}$的素因数，否则因为合数有至少两个素因数会推出素因数乘积大于$x$的矛盾。代码如下：

typedef pair<int, int> pii;

vector<pii> getDivisor(int x) {
  vector<pii> divi;
  for (int i = 2; i*i <= x; i++) {
    if (x % i == 0) {
      int cnt = 0;
      while (x % i == 0) x /= i, cnt++;
      divi.push_back(make_pair(i, cnt));
    }
  }
  if (x > 1) divi.push_back({x, 1});
  return divi;
}

使用素数筛预处理素数之后能够加速这两个算法。

素数筛

最简单的筛法是埃氏筛法，大部分情况使用这种筛就能够有足够的效率，具体思路就是使用每个素数标记他们的倍数为合数，代码如下：

bool vis[N];
int p[N];
int tot = 0;
void getPrime(int n) {
  vis[1] = true;
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) {
      p[++tot] = i;
      for (int j = i+i; j <= n; j += i) vis[j] = true;
    }
  }
}

还有一种线性的素数筛算法名叫欧拉筛，主要是利用求欧拉函数的方法来求出所有素数，有兴趣的同学可以学习更快的欧拉筛。

如果想要求$[a,b]$内的素数，满足$|a|,|b|$较大而$b-a$比较小，就可以用$\sqrt{b}$内的素数来筛。

积性函数

积性函数$f$满足对于任意互素的$a,b$有$f(ab)=f(a)\times f(b)$，完全积性函数对任意$a,b$有$f(ab)=f(a)\times f(b)$

常见的积性函数有欧拉函数，莫比乌斯函数，约数个数等等，利用积性函数的性质能够方便地求解它们。

对于素因数分解后的$x=\prod_{i=1}^n{p_i^{a_i}}$和积性函数$f$满足$f(x)=\prod_{i=1}^n{f(p_i^{a_i})}$

也就是说对于积性函数来说，一个数的函数值和它每个素因数幂次的函数值的累乘，求解素数幂次的函数值一般更加容易。

了解积性函数的好处在于：如果遇到难以求解或者找不到规律的函数，有可能它是积性函数，能够分解素因数求解后合并。可以假设它是积性函数进行验证和尝试，会比漫无目的地思考有效得多。

比如一个数的约数个数$d(x)=\prod_{i=1}^n{(a_i+1)}$，在知道有这个公式的时候，容易想到可以考虑每个素因数取幂次$0,1,\cdots,a_i$一共$a_i+1$种情况，每个素因数相互独立所以直接累乘即可。可是在不知道这个公式的时候很多时候不一定能够轻易想到分解素因数的思路，而从积性函数的角度则比较容易观察出这条性质。

快速幂

快速幂主要是为了快速求出$a^b$。由于幂函数增长快，通常会求快速幂取模，也就是求$a^b\mod M$。

快速幂就是将指数$b$使用二进制表示，比如$a^5=a^{(101)_2}=a^4\times a^1$

初始令结果$res=1$，枚举$p=1,2,4,8,\cdots$其中$p=2^k$，如果$b$的第$k$位为$1$就将$res$乘以$a^p$

枚举的过程可以通过对一个初始为$a$的临时变量不断平方然后取模来完成。

算法的复杂度是$O(\log b)$，算法竞赛中快速幂是非常常用的算法，实现如下：

ll powmod(ll a,ll b, ll MOD) {
  ll res = 1;
  a %= MOD;
  for (; b; b>>=1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}

由于需要不断平方取模，在使用long long的情况下，最多能够支持模数为$10^9$级别，否则平方就会溢出，这也是为什么经常遇到$10^9+7,10^9+9$的原因。

当模数规模增大的时候，无法直接求出正确的平方取模，可以利用类似快速幂的做法将$a\times a$中的一个$a$按照二进制展开，比如$5\times 5=5\times 4 + 5\times 1$

将快速幂中的乘法替代为上述的乘法之后，快速幂能够支持的规模就能达到$10^{18}$了。

逆元

关于逆元有一篇比较详细的讨论：逆元详解

逆元就是将变化逆转回去的元素。比如对于一般的加法而言元素$a$的逆元就是$-a$，因为$x+a+(-a)=x$。对于一般的乘法而言元素$a$的逆元是$\frac{1}{a}$，因为$x\cdot a\cdot\frac{1}{a}=x$，注意$0$没有乘法逆元。

竞赛中由于结果可能很大，经常需要对计算结果取余数，此时如果没有数论知识就无法计算出正确的结果。最为常见的是结果中需要利用组合数，组合数由于太大没法直接计算取模，需要利用数论知识指导来进行计算。

首先来考虑一下模意义下的运算，对于加法而言有$(a+b)\%M=((a\% M)+(b\% M)) \% M$，由于乘法可以看成加法的累积对于乘法也会有类似的结论。

但是当$b\mid a$时，显然有$(a/b)\% M\neq((a\% M)/(b\% M))\% M$

此处就需要引入模意义下乘法逆元的概念，在模数$M$意义下，元素$a$及其逆元$a^{-1}$有$a\cdot a^{-1}\equiv 1\mod M$

由于任意$a^{-1}+kM$都满足逆元的条件，一般来说只讨论$a^{-1}\in [0,M)$，这样的逆元如果存在那便是唯一的。

逆元满足$(a/b)\equiv a\times b^{-1}\mod M$，因为若有$a=b\times c$，那么$(a/b)\equiv c\equiv c\times b\times b^{-1}\equiv a\times b^{-1}\mod M$

逆元的求解

当$\gcd(a,M)=1$或者说$a,M$互质的情况下，元素$a$关于模数$M$存在逆元。

当$M$为质数的时候能够使用费马小定理求解逆元，这种方法是最为方便常用的，只需要使用快速幂取模。

当$M$不是素数，但$a,M$互质的时候，可以使用扩展欧几里得求解逆元。

在逆元详解中还讨论了线性处理逆元表的方法，还有其他逆元的求解方法和应用。

费马小定理

费马小定理：对于质数$M$而言，有$a^{M}\equiv a\mod M$

当$a,M$互质或者说$a$不是$M$的倍数的时候，就有：

$$a^{M-1}=a\times a^{M-2}\equiv 1\mod M$$

根据逆元的定义容易发现$a^{M-2}$是元素$a$的逆元，利用快速幂求解$a^{M-2}\% M$即可。

为了方便，竞赛题目经常给出$10^9+7,10^9+9$之类的大素数，使用费马小定理能够解决大多数使用逆元的场景。

费马小定理是数论四大定理之一，它也是另一个四大定理欧拉定理的特例，利用欧拉定理和欧拉函数能够解决更困难的问题。

组合数取模

组合数是统计求解时非常常用的工具，$C_n^m$给出了在$n$个不同物品中选取$m$个物品的方案数。

求解组合数取模首先可以利用组合数公式$C_n^m=\frac{n!}{m!\cdot(n-m)!}$，这种方法只能处理很小的数据。

优化一些的话，可以利用组合数的递推公式$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$，枚举最后一个元素选不选，选就是$C_{n-1}^{m-1}$，不选就是$C_{n-1}^m$，这种方法能够处理$10^3$级别的数据。代码如下：

for (int i = 0; i < N; i++) {
  C[i][0] = 1;
  for (int j = 1; j <= i; j++) {
    C[i][j] = (C[i-1][j-1] + C[i-1][j]) % M;
  }
}

上述方法有些时候仍然没有办法满足需求，当模数$M$为素数时可以利用费马小定理求解组合数取模。

将组合数公式变形可以获得如下结果：

$$C_n^m=\frac{n!}{m!\cdot(n-m)!}\equiv n!\times (m!)^{-1}\times((n-m)!)^{-1}\mod M$$

利用递推预处理所有$n!\%M$，然后利用费马小定理求解逆元就能获得如下公式：

1
2
3

ll C(int n, int m) {
  return fac[n] * inv(fac[m], M) % M * inv(fac[n-m], M) % M;
}

当模数$M$比较小，达到$10^6$级别的时候，可以通过 Lucas定理求解$n,m$很大的组合数。

当模数是合数而且素因数都不大的时候，可以对$M$分解素因数，利用 Lucas定理求出组合数模每个素因数的余数再用中国剩余定理合并结果。

矩阵定义

矩阵通常是指这样的东西：$\begin{bmatrix}1 & 2\\ 3 & 4\end{bmatrix}\newcommand{\x}{\boldsymbol{x}}\newcommand{\b}{\boldsymbol{b}}\newcommand{\y}{\boldsymbol{y}}\newcommand{\A}{\boldsymbol{A}}\newcommand{\B}{\boldsymbol{B}}\newcommand{\C}{\boldsymbol{C}}$

矩阵有$n$行$m$列，一共$n\times m$个元素，第$i$行第$j$列的元素为$\A_{i,j}$，矩阵一般记作大写粗体字母。

特别的，$1\times n$的矩阵被称为行向量，$n\times 1$的矩阵被称为列向量，第$i$个元素为$\x_i$，向量一般记作小写粗体字母。

向量有多少个元素就称它有多少维，$n\times m$的矩阵也可以看做是$m$个$n$维列向量或者$n$个$m$维行向量。

形状相同的矩阵能够进行加法，产生一个形状一样的矩阵。若$\C=\A+\B$则有：$\C_{i,j}=\A_{i,j}+\B_{i,j}$

矩阵乘法

矩阵中最基础的乘法是$n$维行向量$\x$乘以$n$维列向量$\y$获得一个值，表示为$\x\cdot \y=v$

行向量乘以列向量的结果为他们第$i$维值相乘后累加的结果，向量乘法又称为点积：

$$\x\cdot\y=\sum_{i=1}^n{\x_i\cdot \y_i}$$

点积能够表达$n$元一次方程：

$$ \begin{bmatrix}1 & 2\end{bmatrix} \begin{bmatrix}x\\ y\end{bmatrix}= \begin{bmatrix}x+2y\end{bmatrix}$$

矩阵和向量也可以进行乘法，要求是$n\times m$的矩阵$\A$乘以$m\times 1$的列向量$\x$，获得一个$n\times 1$的列向量$\b$。

可以将矩阵和向量的乘法看做矩阵中的$n$个$m$维行向量分别和列向量做点积，获得结果的每一维：

$$\begin{bmatrix}1 & 2\\ 3 & 4\\ 5 & 6\end{bmatrix} \begin{bmatrix}x\\ y\end{bmatrix}=\begin{bmatrix}x+2y\\3x+4y\\5x+6y\end{bmatrix}=\begin{bmatrix}3\\ 7\\ 11\end{bmatrix}$$

向量相等需要每一个分量，以上乘法可以看做两元一次方程组的另一种表达形式。

任意的$n$元一次方程组均可以表达为$\A\x=\b$，其中$\A$为参数，$\x$为未知量，$\b$为结果。

有了上述定义之后，能够比较容易推导出矩阵之间的乘法。

矩阵乘法要求$n\times m$的矩阵$\A$乘以$m\times p$的矩阵$\B$，获得一个$n\times p$的矩阵$\C$。

矩阵乘法能够拆分为矩阵和向量的乘法，看做是$\A$乘以$\B$中的第$i$列，获得$\C$中的$i$列：

$$\begin{align*}\A \B &= \A \begin{bmatrix} \B_{*,1} & \B_{*,2} & \cdots & \B_{*,p}\end{bmatrix}\\ &= \begin{bmatrix} \A \B_{*,1} & \A \B_{*,2} & \cdots & \A \B_{*,p}\end{bmatrix} \\ &= \begin{bmatrix}\C_{*,1} & \C_{*,2} & \cdots & \C_{*,p}\end{bmatrix}\\ &= \C\end{align*}
$$

同时根据矩阵和向量乘法和向量点积的运算规则，能够推导出以下公式，该公式很容易使用计算机计算：

$$\C_{i,j}=\sum_{k=1}^m{\A_{i,k}\B_{k,j}}$$

矩阵乘法满足结合律$(\A\B)\C=\A(\B\C)$，当然矩阵需要能够进行相乘才行。矩阵乘法不满足交换律。

容易发现矩阵乘法运算的复杂度为$O(nmp)$。

矩阵快速幂

矩阵快速幂在算法竞赛中非常常见，常常用来优化递推的问题，虽然选手们常称之为dp。

矩阵快速幂就是用来运算$\A^p$的，算法的思路和普通快速幂一样，只是乘法运算为矩阵的乘法。

由于需要能和自身做乘法运算，矩阵快速幂运算需要作用于方阵，即$n\times n$的矩阵。

$n$维行向量乘以$\A^p$会获得一个$n$维行向量，$\A^p$乘以$n$维列向量会获得一个$n$维列向量。

矩阵快速幂的方阵根据结合律可以先拆出来和向量做乘法，这个乘法可以看做向量维度不变但数值变化的一次变换。

考虑斐波那契数列，有$F_0=F_1=1$满足递推关系$F_i=F_{i-1}+F_{i-2}$。

该递推关系可以看做是线性方程，能够发现$F_{i+2}=\begin{bmatrix}1 & 1\end{bmatrix}\begin{bmatrix}F_i\\ F_{i+1}\end{bmatrix}$

需要对同一个维度的向量不断变换，所以左边也要是两维，凑一下得到：

$$\begin{bmatrix}F_{i+1}\\F_{i+2}\end{bmatrix}=\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}\begin{bmatrix}F_i\\ F_{i+1}\end{bmatrix}$$

将所有的转换矩阵表示成幂次的形式，可以获得如下方程：

$$\begin{bmatrix}F_{n}\\F_{n+1}\end{bmatrix}=\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}^n\begin{bmatrix}F_0\\ F_1\end{bmatrix}$$

对变换矩阵做矩阵快速幂后再做一次矩阵和向量的乘法就能够获得结果，矩阵快速幂的复杂度为$O(n^3\log p)$