素数，约数，同余。

基础数论

常见的思维方法有：观察与分析、概括与抽象、分析与综合、特殊与一般、类比、归纳和演绎等；

常见的数学思想有：函数与方程思想、数形结合思想、分类讨论思想、转化（化归）思想等。

之所以先介绍这些，是因为这些东西确实很重要，在算法竞赛中蕴含得特别多，最常见的就是分类讨论，其他思想其实也特别多。

素数

素数的判定

枚举 $2$ 到 $\sqrt n$ 的数暴力判定。

素数筛

主要掌握埃氏筛和线性筛，并理解二者的原理，会魔改。

素因数分解

单个数素因数分解

对单个数的素因数分解，只需要从 $2$ 枚举到 $\sqrt n$ ，对于每次枚举到的约数，不断让 $n$ 除之，统计除法次数，直到除不开。最后如果剩下的部分大于 $1$ ，则剩下的部分也是一个素数。可以证明，这样做下去我们只有在枚举到质数的时候才会真正做除法。

阶乘素因数分解

本需求会在高精度组合数计算中被用到。

分别对每个数进行分解的复杂度是 $O(n\sqrt n)$ ，数据范围比较大的时候难以承受。

另一种方法是先筛出 $n$ 范围内的所有素数，然后枚举素数，统计每个素数的贡献，即直接统计每个素数在阶乘中出出现了多少次，手段是不断除以这个素数$p$，第$k$次做除法得到的商，就代表有多少$1$到 $n$ 之间的数含有$p$的最高次数是$p^k$。这种方法需要$O(n)$预处理素数，然后$O(\sum \log_pn)$ 的时间统计所有素数的贡献。考虑到 $1$ 到 $n$ 的素数个数大约是$O(\frac{n}{\ln n})$级别的，所以做放缩，知$\sum \log_p n \leq \frac{n}{\ln n} \log_2 n$ ，利用换底公式可知右式的渐进上界是 $O(n)$ 。

参考代码如下：

// flag = 1 或 -1
void split(int n, int flag) {
    for (int i = 0; i < cnt; i++) {
        int p = prime[i];
        while (p <= n) {
            primeidx[i] += (flag * (n / p));
            p = p * prime[i];
        }
    }
}

约数

约数之和

求一系列数的乘积所得到的数的所有的约数之和。

先对每个数做素因数分解，然后使用生成函数的思想，可知最后的结果为

$ans = \prod_{i = 1}^{k}\sum_{j = 0}^{\alpha_i}p_{i}^j$

根据数据范围，选择使用秦九韶算法，分治或者等比数列求和公式进行计算即可。

最大公约数

辗转相除

最常用的方法。

更相减损

弱化版的辗转相除。

高精度gcd

高精度gcd常用更相减损术去做，因为高精度的取模不好写。

互素与欧拉函数

欧拉函数的定义是：$\phi(x)$定义为 $1$ 到 $x$ 中与 $x$ 互素的数的个数。

容易发现，对素数 $p$ 来说，$\phi(p) = p - 1$ 。

$\phi(x)$ 的计算公式容易理解：

$\phi(x) = x \times(1 - \frac{1}{p_1})\times(1 - \frac{1}{p_2})...\times(1 - \frac{1}{p_k})$

可以从概率的角度/容斥原理的角度去考虑这个公式（有多大概率取到不是$p_i$的倍数的数）。

考虑 $c = a\times b$，如果有 $\gcd(a, b) = 1$ ，则由上述计算公式中，可以发现 $\phi(c) = \phi(a)\times \phi(b)$ （因为没有相同素因子）

如果 $\gcd(a,b) \ne 1$ ，倘若 $a$ 为素数，那么也是有很好的性质的。因为 $a$ 为素数，且 $\gcd(a, b) \neq 1$ ，所以 $\gcd(a, b) = a$ ，考虑到 $\phi(a)$ 和 $\phi(b)$ 的计算式，可以发现 $\phi(c) = a \times \phi(b)$ 。

利用线性筛，可以 $O(n)$ 的时间预处理出 $\phi(x)$ 。

同余

贝祖定理

若 $\gcd(a, b) = d$ ，那么存在整数 $x, y$ ，使得 $ax + by = d$​ 成立。

显然，若 $d$ 不能整除 $c$ ，那么 $ax + by = c$​ 一定没有整数解。

特殊地，$\gcd(a, b) = 1$ 时，存在整数 $x, y$ ，使得 $ax + by = 1$ 成立。

中国剩余定理

普通CRT

对于同余方程组

$\begin{cases} x\equiv a_1(mod\ m_1)\\ x\equiv a_2(mod\ m_2)\\ ...\\ x\equiv a_n(mod\ m_n)\\ \end{cases}$

其中$\gcd(m_i, m_j) = 1$ ，$1\leq i, j\leq n,i \neq j$

设$M = \prod\limits_{i = 1}^nm_i$，$M_i = \frac{M}{m_i}$，$M_i^{-1}M_i\equiv1(mod\ m_i)$

则 $x\equiv\sum\limits_{i= 1}^{n}M_i^{-1}M_ib_i(mod\ m_j),\forall 1\leq j\leq n$

即我们给出了一个构造 $x $ 的方式。容易验证上式成立。

在求$M_i^{-1}$ 时，注意到$\gcd(M_i^{-1}, m_i) = 1$ ，所以可以使用 exgcd 进行求解，而使用其他的方法求可能会求不出来（exgcd 只要有数和模数互素即可，而其他的方法需要模数是素数）。

exCRT

对于上述同余方程组，当不满足模数两两互素的时候，要想构造出 $x$ ，就需要使用扩展中国剩余定理了。

扩展中国剩余定理的思路是逐步两两合并方程：

$\begin{cases} x\equiv a_1(mod\ m_1)\\ x\equiv a_2(mod\ m_2) \end{cases}$

改写成等式：

$\begin{cases} x = m_1p+a_1\\ x = m_2q+a_2 \end{cases}$

需要有合适的整数使得$p, q$ 都是整数，所以 $m_1p - m_2q = a_2 - a_1$ 要有整数解，所以$\gcd(m_1, m_2)\mid(a_2 - a_1)$ 才能保证有合适的 $x$ 。

费马小定理

主要用来求解模数是质数时的逆元。

如果 $\gcd(a,p) = 1$ ，那么 $a^p \equiv a(mod\ p)$ ，特别的，当 $p$ 为质数时，有 $a^{p - 1}\equiv1(mod\ p)$

哥德巴赫猜想

TODO

虽然是猜想，但是在很大的范围内验证是对的，所以有时候会用来做一些判断。

exgcd

用于求解二元一次方程的整数解，很多时候是求解包含逆元未知数的二元一次方程。

exgcd 的原理是，考虑辗转相除的过程，gcd(a, b) = gcd(b, a % b), b != 0

不妨设 $\gcd(a, b) = d$ ，第 $i$ 次迭代时得到的方程是 $a_ix + b_iy = d$ ，则有：

$a_nx + b_ny = a_{n + 1}x + b_{n + 1}y = d$

进一步，使用 $\gcd(a, b) = \gcd(b, a \% b)$ （在没有到递归边界的时候），有：

$a_nx + b_ny = b_nx + (a_n \% b_n)y = d$

利用等式 $a \% b = a -[ \frac{a}{b}]b$​，代换之后有：

$a_nx + b_ny = b_nx + (a_n -[ \frac{a_n}{b_n}]b_n)y = d$

线性同余方程

形如 $ax\equiv b(mod\ m)$​ ，可以转化为 $ax + my = b$​ ，根据贝祖定理，有整数解的充要条件是 $\gcd(a, m) \mid b$​

高次同余方程