一、数论中的基本概念与性质

1、整除

定义

若整数$b$除以非零整数$a$，商为整数，且余数为零，我们就说$b$能被$a$整除（或说$a$能整除$b$），表示为$a \mid b$

性质

(1)反身性

$a \mid a$
证明：
$\because a \div a=1$
$\therefore a \mid a$

(2)反对称性

$a \mid b$且$b \mid a$则$\left\vert a \right\vert=\left\vert b \right\vert$
证明：
$\because a \mid b,b \mid a$
$\therefore$设$b \div a=x,a \div b=y \left(x,y \in Z\right)$
$\therefore \begin{cases}b=ax\\a=by\end{cases}$
$\therefore b=ax=bxy$
$\therefore xy=1$
$\therefore \begin{cases} x= \pm 1\\y= \pm 1\end{cases}$
$\therefore \left\vert a \right\vert=\left\vert b \right\vert$
$\left\vert a \right\vert=\left\vert b \right\vert$则$a \mid b$且$b \mid a$
证明：
$\because \left\vert a \right\vert=\left\vert b \right\vert$
$\therefore \begin{cases} a \div b= \pm 1\\b \div a= \pm 1\end{cases}$
$\therefore a \mid b$且$b \mid a$

(3)传递性

$a \mid b$且$b \mid c$则$a \mid c$
证明：
$\because a \mid b,b \mid c$
$\therefore$设$b \div a=x,c \div b=y \left(x,y \in Z\right)$
$\therefore \begin{cases}b=ax\\c=by\end{cases}$
$\therefore c=by=axy$
$\therefore c \div a=xy$
$\therefore a \mid c$

(4)其他性质

①$a \mid b$且$a \mid c$且$a \mid d$则$a \mid \left(ka+mb+nc+ld\right)$
证明：
$\because a \mid b,a \mid c,a \mid d$
$\therefore$设$b \div a=x,c \div a=y,d \div a=z \left(x,y,z \in Z\right)$
$\therefore \begin{cases}b=ax\\c=ay\\d=az\end{cases}$
$\therefore \left(ka+mb+nc+ld\right) \div a=\left(ka+mxa+nya+lza\right) \div a=\left(k +mx+ny+lz\right)$
$\therefore a \mid \left(ka+mb+nc+ld\right)$
②质数$p \mid ab$则$p \mid a$或$p \mid b$
证明：
假设$p \nmid a$且$p \nmid b$
$\because p \nmid a,p \nmid b$
$\therefore a$中不含有质因子$p$，$b$中不含有质因子$p$
$\therefore ab$中不含有质因子$p$
$\therefore p \nmid ab$，与$p \mid ab$矛盾
$\therefore$假设不成立
$\therefore p \mid a$或$p \mid b$
③连续$n$个整数中恰有一个整数是$n$的倍数
证明：
设这$n$个数为$a,a+1,\cdots,a+n-1,a \equiv r \pmod{n},1 \leqslant r \leqslant n$
$\therefore \left(a+n-r\right) \equiv \left(r+n-r\right) \equiv n \equiv 0 \pmod{n}$
又$\because 0 \leqslant n-r < n$
$\therefore n \mid \left(a+n-r\right)$
$\therefore$连续$n$个整数中恰有一个整数是$n$的倍数
④连续$n$个整数的乘积为$n!$的倍数
证明：
设这$n$个数为$a,a+1,\cdots,a+n-1$
$\because C_{a+n-1}^{n}=\frac{\prod \limits_{i=1}^n \left(a+n-i\right)}{n!}$为整数
$\therefore n! \mid \prod \limits_{i=1}^n \left(a+n-i\right)$

2、质数与合数

定义

(1)质数

一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数

(2)合数

合数指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数

性质

质数无穷多

证明（质数无穷多的证明方法有许多，这里只展示1种，~~其实我知道两种~~，感兴趣的可以上网查）：
假设质数只有$n$个
从小到大依次排列为$p_{1},p_{2}, \cdots ,p_{n}$，设$N=\prod \limits_{i=1}^n p_{i}$
$\because p_{1} \nmid N$,$p_{2} \nmid N,\cdots,p_{n} \nmid N$
$\therefore N$为质数，与质数只有$n$个矛盾
$\therefore$假设不成立
$\therefore$质数无穷多

算术基本定理

每一个合数都可以以唯一形式被写成质数的乘积
证明：
假设合数可以以多种方式写成多个质数的乘积，设最小的是$n$
设$n=\prod \limits_{i=1}^{r}(p_{i}^{a_{i}})=\prod \limits_{i=1}^{s}(q_{i}^{b_{i}})$
$\because p_{1} \mid \prod \limits_{i=1}^{s}(q_{i}^{b_{i}})$
$\therefore q_{1}^{b_{1}},q_{2}^{b_{2}},\cdots,q_{s}^{b_{s}}$中有一个数能被$p_{1}$整除
$\therefore$不妨设为$q_{1}$
又$\because q_{1}$也是质数，因此$q_{1}=p_{1}$
假设$a_{1} > b_{1}$
$\therefore p_{1}^{a_{1}-b_{1}} \prod \limits_{i=2}^{r}(p_{i}^{a_{i}})=\prod \limits_{i=2}^{s}(q_{i}^{b_{i}})$
$\therefore q_{2}^{b_{2}},q_{3}^{b_{3}},\cdots,q_{s}^{b_{s}}$中有一个数能被$p_{1}$整除
又$\because p_{1}=q_{1} \ne q_{i}(i \ne 1)$
$\therefore a_{1} \leqslant b_{1}$
同理，$\therefore a_{1} \geqslant b_{1}$
$\therefore a_{1} = b_{1}$
$\therefore$存在小于$n$的整数$m=\prod \limits_{i=2}^{r}(p_{i}^{a_{i}})=\prod \limits_{i=2}^{s}(q_{i}^{b_{i}})$可以用多于一种的方式写成多个质数的乘积，这与$n$的最小性矛盾
$\therefore$ 每一个合数都可以以唯一形式被写成质数的乘积

3、最大公约数和最小公倍数

定义

(1)约数与倍数

如果整数$a$能被整数$b$整除，$a$就叫做$b$的倍数，$b$就叫做$a$的约数

(2)公约数与公倍数

几个整数中公有的约数，叫做这几个整数的公约数；几个整数中公有的倍数，叫做这几个整数的公倍数

(3)最大公约数与最小公倍数

几个整数的公约数中，最大的一个，叫做这几个数的最大公约数；几个整数的公倍数中，最小的一个，叫做这几个数的最小公倍数数

(4)互质

$\forall a,b \in N$,若(a,b)=1,则称$a,b$互质

(5)欧拉函数

$1$~$N$中与$N$互质的数的个数被称为欧拉函数，记为$\varphi \left(N\right)=N \times \prod \limits_{质数p|N}(1-\frac{1}{p})$

(6)积性函数

如果当$a,b$互质，有$f \left(ab\right)=f \left(a\right) \times f \left(b\right)$，那么称函数$f$为积性函数

性质

①$\forall a,b \in Z$，$gcd\left(a,b\right) \times lcm\left(a,b\right)=ab$
证明：
设$gcd\left(a,b\right)=d,a=a_{0}d,b=b_{0}d,(a_{0},b_{0})=1$
$lcm\left(a,b\right)=lcm\left(a_{0},b_{0}\right) \times d=a_{0}b_{0}d$
$\therefore gcd\left(a,b\right) \times lcm\left(a,b\right)=d \times a_{0}b_{0}d=a_{0}b_{0}d^{2}=\left(a_{0}d\right) \times \left(b_{0}d\right)=ab$
②$\forall n > 1,1-n$中与$n$互质的数的和为$\frac{n \times \varphi \left(n\right)}{2}$
证明：
$\because gcd \left(n,x\right)=gcd \left(n,n-x\right)$
$\therefore$与$n$不互质的数$x,n-x$成对出现，平均值为$\frac{n}{2}$
$\therefore1-n$中与$n$互质的数的和为$\frac{n \times \varphi \left(n\right)}{2}$
③欧拉函数是积性函数
若$a,b$互质，则$\varphi \left(ab\right)=\varphi \left(a\right) \times \varphi \left(b\right)$
证明：
设$a=\prod \limits_{i=1}^{r}(p_{i}^{a_{i}}),b=\prod \limits_{i=1}^{s}(q_{i}^{b_{i}})$
$\therefore \varphi \left(a\right)=a \times \prod \limits_{i=1}^{r}(1-\frac{1}{p_{i}}),\varphi \left(b\right)=b \times \prod \limits_{i=1}^{s}(1-\frac{1}{q_{i}})$
$\therefore \varphi \left(ab\right)=ab \times \prod \limits_{i=1}^{r}(1-\frac{1}{p_{i}}) \times \prod \limits_{i=1}^{s}(1-\frac{1}{q_{i}})=\varphi \left(a\right) \times \varphi \left(b\right)$

4、同余

定义

(1)同余

若整数$a$和整数$b$除以正整数$m$的余数相等，则称$a,b$模$m$同余，记为$a \equiv b \pmod{m}$

(2)同余类

对于$\forall a \in \left[0,m-1\right]$，集合$\left\{a+km\right\}(k \in Z)$的所有数模$m$同余，余数都是$a$，该集合称为一个模$m$的同余类，简记为$\overline{a}$

(3)完全剩余系

模$m$的同余类一共有m个，分别为$\overline{0} , \overline{1} , \cdots , \overline{m-1}$,它们构成$m$的完全剩余系

(4)简化剩余系

$1-m$中与$m$互质的数代表的同余类共有$\varphi \left(m\right)$个，它们构成$m$的简化剩余系

(5)数论倒数（乘法逆元）

若整数$a,x$满足$ax \equiv 1 \pmod{b}$，则$x$为$a$对模$m$意义下的数论倒数（乘法逆元）记为$a^{-1} \pmod{m}$

性质

(1)同余的充要条件

$a \equiv b \pmod{m}$的充要条件是$m \mid \left(a-b\right)$
证明：
$\because m \mid \left(a-b\right)$
$\therefore$存在整数$t$使得$a-b=mt$
$\therefore a=b+mt$
$\therefore a \equiv b \pmod{m}$

$\because a \equiv b \pmod{m}$
$\therefore$存在整数$t$使得$a=b+mt$
$\therefore a-b=mt$
$\therefore m \mid \left(a-b\right)$

(2)反身性

$a \equiv a \pmod{m}$
证明：
$\because a-a=0,m \ne 0$
$\therefore m \mid a-a$
$\therefore a \equiv a \pmod{m}$

(3)对称性

$a \equiv b \pmod{m}$则$b \equiv a \pmod{m}$
证明：
$\because a \equiv b \pmod{m}$
$\therefore m \mid \left(a-b\right)$
$\therefore m \mid \left(b-a\right)$
$\therefore b \equiv a \pmod{m}$

(4)传递性

$a \equiv b \pmod{m}$且$b \equiv c \pmod{m}$则$a \equiv c \pmod{m}$
$\because a \equiv b \pmod{m}$
$\therefore m \mid \left(a-b\right)$
又$\because b \equiv c \pmod{m}$
$\therefore m \mid \left(b-c\right)$
$\therefore m \mid \left[\left(a-b\right)+\left(b-c\right)\right]$
$\therefore m \mid \left(a-c\right)$
$\therefore a \equiv c \pmod{m}$

(5)可加性

$a \equiv b \pmod{m}$且$c \equiv d \pmod{m}$则$a+c \equiv b+d \pmod{m}$
证明：
$\because a \equiv b \pmod{m}$
$\therefore m \mid \left(a-b\right)$
又$\because c \equiv d \pmod{m}$
$\therefore m \mid \left(c-d\right)$
$\therefore m \mid \left[\left(a-b\right)+\left(c-d\right)\right]$
$\therefore m \mid \left[\left(a+c\right)-\left(b+d\right)\right]$
$\therefore a+c \equiv b+d \pmod{m}$

(6)可减性

$a \equiv b \pmod{m},c \equiv d \pmod{m}$则$a-c \equiv b-d \pmod{m}$
证明：
$\because a \equiv b \pmod{m}$
$\therefore m \mid \left(a-b\right)$
又$\because c \equiv d \pmod{m}$
$\therefore m \mid \left(c-d\right)$
$\therefore m \mid \left[\left(a-b\right)-\left(c-d\right)\right]$
$\therefore m \mid \left[\left(a-c\right)-\left(b-d\right)\right]$
$\therefore a-c \equiv b-d \pmod{m}$

(7)可乘性

①$a \equiv b \pmod{m}$则$ac \equiv bc \pmod{m}$
证明：
$\because a \equiv b \pmod{m}$
$\therefore m \mid \left(a-b\right)$
$\therefore m \mid \left(a-b\right)c$
$\therefore m \mid \left(ac-bc\right)$
$\therefore ac \equiv bc \pmod{m}$
②$a \equiv b \pmod{m},c \equiv d \pmod{m}$则$ac \equiv bd \pmod{m}$
证明：
$\because a \equiv b \pmod{m}$
$\therefore ac \equiv bc \pmod{m}$
又$\because c \equiv d \pmod{m}$
$\therefore bc \equiv bd \pmod{m}$
$\therefore ac \equiv bd \pmod{m}$

(8)有关同余的其他性质

①$ac \equiv bc \pmod{m}$且$\left(m,c\right)=1$则$a \equiv b \pmod{m}$
证明：
$\because ac \equiv bc \pmod{m}$
$\therefore m \mid \left(ac-bc\right)$
$\therefore m \mid \left(a-b\right)c$
又$\because \left(m,c\right)=1$
$\therefore m \mid \left(a-b\right)$
$\therefore a \equiv b \pmod{m}$
②$ac \equiv bc \pmod{mc}$则$a \equiv b \pmod{m}$
证明：
$\because ac \equiv bc \pmod{mc}$
$\therefore mc \mid \left(ac-bc\right)$
$\therefore m \mid \left(a-b\right)$
$\therefore a \equiv b \pmod{m}$

(9)有关完全剩余系的性质

$gcd\left(m,a\right)=1$且$\left\{\overline{b_{i}}\right\}\left(i\in \left[1,m\right]\right)$是模$m$的一个完全剩余系，则$\left\{\overline{ab_{i}}\right\}\left(i\in \left[1,m\right]\right)$也是模$m$的一个完全剩余系
证明：
假设存在两个整数$a \times b_{i} \equiv a \times b_{j} \pmod{m}$
$b_{i} \equiv b_{j} \pmod{m}$，与$\left\{\overline{b_{i}}\right\}\left(i\in \left[1,m\right]\right)$是模$m$的一个完全剩余系矛盾
$\therefore$假设不成立
$\therefore \left\{\overline{ab_{i}}\right\}\left(i\in \left[1,m\right]\right)$是模$m$的一个完全剩余系

(10)有关简化剩余系的性质

$gcd\left(m,a\right)=1$且$\left\{\overline{b_{i}}\right\}\left(i\in \left[1,\varphi \left(m\right)\right]\right)$是模$m$的一个简化剩余系，则$\left\{\overline{ab_{i}}\right\}\left(i\in \left[1,\varphi \left(m\right)\right]\right)$也是模$m$的一个完全剩余系
证明：
假设存在两个整数$a \times b_{i} \equiv a \times b_{j} \pmod{m}$
$b_{i} \equiv b_{j} \pmod{m}$，与$\left\{\overline{b_{i}}\right\}\left(i\in \left[1,m\right]\right)$是模$m$的一个简化剩余系矛盾
$\therefore$假设不成立
$\therefore \left\{\overline{ab_{i}}\right\}\left(i\in \left[1,m\right]\right)$是模$m$的一个简化剩余系

(11)费马小定理

若$p$是质数，则对任意与$p$互质的整数$a$，有$a^{p-1} \equiv 1 \pmod{p}$
证明：
设$p$的完全剩余系为$\left\{\overline{i}\right\}\left(i \in\left[1,p-1\right]\right)$
$\because gcd\left(a,p\right)=1$
$\therefore \{\overline{ai}\}(i\in\left[1,p-1\right])$也是$p$的一个完全剩余系
$\therefore$对于每一个$i(i\in\left[1,p-1\right])$，总存在一个$j$使得$i \equiv a \times j \pmod{p}$
$\therefore \left(p-1\right)! \equiv \left(p-1\right)! \times a^{p-1} \pmod{p}$
又$\because \left(p,\left(p-1\right)!\right)=1$
$\therefore a^{p-1} \equiv 1 \pmod{p}$

(12)欧拉定理

$gcd\left(a,n\right)=1,a \in Z^{+}$，则$a^{\varphi \left(n\right)} \equiv 1 \pmod{n}$
证明：
设$n$的简化剩余系为$\left\{\overline{a_{i}}\right\}\left(i \in\left[1,\varphi\left(n\right)\right]\right)$
$\because gcd\left(a,n\right)=1$
$\therefore \{\overline{aa_{i}}\}(i\in\left[1,\varphi \left(n\right)\right])$也是$p$的一个化简剩余系
$\therefore$对于每一个$a_{i}(i\in\left[1,\varphi \left(n\right)\right])$，总存在一个$j$使得$i \equiv a \times a_{j} \pmod{p}$
$\therefore \prod \limits_{i=1}^{\varphi \left(n\right)} a_{i} \equiv \prod \limits_{i=1}^{\varphi \left(n\right)}a_{i} \times a^{\varphi \left(n\right)} \pmod{n}$
$\therefore a^{\varphi \left(n\right)} \equiv 1 \pmod{n}$

(13)欧拉定理推论

$gcd\left(a,n\right)=1,a \in Z^{+}$，则对于任意的正整数$b$，有$a^b \equiv a^{b \% \varphi \left(n\right)} \pmod{n}$
证明：
设$b=q \times \varphi \left(n\right)+r,0 \leqslant r < \varphi \left(n\right)$
$a^{b} \equiv a^{q \times \varphi \left(n\right)+r} \equiv \left(a^{\varphi \left(n\right)}\right)^{q} \times a^{r} \equiv 1^{q} \times a^{r} \equiv a^{r} \equiv a^{b \% \varphi \left(n\right)} \pmod{n}$

5、不定方程（丢番图方程）

定义

不定方程是指未知数的个数多于方程个数，且未知数受到某些限制（如要求是有理数、整数或正整数等等）的方程或方程组

性质

(1)裴蜀Bézout定理

对于任意正整数$a,b$，存在一对整数$x,y$，满足$ax+by=gcd\left(a,b\right)$
证明：
设$gcd\left(a,b\right)=d,a=a_{0}d,b=b_{0}d$
$aa_{0}+bb_{0}=1$
$\therefore \left(a_{0},b_{0}\right)$是方程$ax+by=\left(a,b\right)$的一组解

(2)所有解与特解的关系

$\left(x_{0},y_{0}\right)$是方程$ax+by=c$的一组整数解，则方程的所有解为$\begin{cases}x=x_{0}+\frac{b}{gcd\left(a,b\right)}t\\y=y_{0}-\frac{a}{gcd\left(a,b\right)}t\end{cases},t \in Z$
证明：
设$ax_{1}+by_{1}=c,gcd\left(a,b\right)=c_{0},a=a_{0}c_{0},b=b_{0}c_{0},gcd\left(a_{0},b_{0}\right)=1$
$a_{0}x_{0}+b_{0}y_{0}=c_{0},a_{0}x_{1}+b_{0}y_{1}=c_{0}$
$\therefore a_{0}x_{0}+b_{0}y_{0}=a_{0}x_{1}+b_{0}y_{1}$
$\therefore a_{0}\left(x_{0}-x_{1}\right)=b_{0}\left(y_{1}-y_{0}\right)$
$\therefore b_{0} \mid a_{0}(x_{0}-x_{1})$
$\therefore b_{0} \mid \left(x_{0}-x_{1}\right)$
$\therefore x_{0} \equiv x_{1} \pmod{b_{0}}$
同理，$\therefore y_{0} \equiv y_{1} \pmod{b_{0}}$
$\therefore \begin{cases}x=x_{0}+b_{0}t\\y=y_{0}-a_{0}t\end{cases}$
$\therefore \begin{cases}x=x_{0}+\frac{b}{gcd\left(a,b\right)}t\\y=y_{0}-\frac{a}{gcd\left(a,b\right)}t\end{cases}$

(3)其他性质

①$gcd\left(a,b\right)=1,a,b \in Z^{+}$，则方程$ax+by=ab-a-b$没有非负整数解
证明：
$\because ax+by=ab-a-b$
$\therefore a \left(x+1\right)+b \left(y+1\right)=ab$
又$\because a \mid ab$
$\therefore a \mid \left(a \left(x+1\right)+b \left(y+1\right)\right)$
$\therefore a \mid b \left(y+1\right)$
又$\because gcd\left(a,b\right)=1$
$\therefore a \mid \left(y+1\right)$
②$gcd\left(a,b\right)=1,c>ab-a-b,a,b,c \in Z^{+}$，则方程$ax+by=c$有非负整数解
证明：
$\because gcd\left(a,b\right)=1$
$\therefore$设$ax_{0}+by_{0}=c,0 \leqslant x_{0} \leqslant b-1$
$\therefore y_{0}=\frac{c-ax_{0}}{b}>\frac{ab-a-b-ax_{0}}{b} \geqslant \frac{ab-a-b-a\left(b-1\right)}{b}=-1$
$\therefore y_{0} \geqslant 0$
$\therefore x_{0},y_{0}$为非负整数
$\therefore$方程$ax+by=c$有非负整数解
③$gcd\left(a,b\right)=1,a,b \in Z^{+},0 \leqslant c \leqslant ab-a-b$，则恰有$\frac{\left(a-1\right)\left(b-1\right)}{2}$个整数$c$不能表示成$ax+by$的形式，$x,y \in \N$

6、同余方程

定义

设$f(x)=\sum \limits_{i=0}^{n}a_{i}x^{i}$是整系数多项式，称$f(x) \equiv 0 \pmod{m}$是$x$模$m$的同余方程

7、高斯函数

定义

(1)取整函数

不超过实数$x$的最大整数称为$x$的整数部分，记作$\left[x\right]$

(2)取小函数

实数$x$的非负纯小数部分，记作$\left\{x\right\}$

性质

①$x=\left[x\right]+\left\{x\right\}$
②$x-1<\left[x\right] \leqslant x$
③$0 \leqslant \left\{x\right\}<1$
④若$x \leqslant y$，则$\left[x\right] \leqslant \left[y\right]$
证明：
$\because \left[x\right] \leqslant x \leqslant y<\left[y\right]+1$
$\therefore \left[x\right] \leqslant \left[y\right]$
⑤$\forall a \in Z^{*},b \in Z$，则$b=a \left[\frac{b}{a}\right]+a\left\{\frac{b}{a}\right\},a\left\{\frac{b}{a}\right\} \in Z$
证明：
$\because \frac{b}{a}=\left[\frac{b}{a}\right]+\left\{\frac{b}{a}\right\}$
$\therefore b=a \left[\frac{b}{a}\right]+a\left\{\frac{b}{a}\right\}$
$\therefore a\left\{\frac{b}{a}\right\}=b-a \left[\frac{b}{a}\right]$
$\therefore a\left\{\frac{b}{a}\right\} \in Z$
⑥$\left[x\right]+\left[y\right]=\left[x+y\right]$或$\left[x+y\right]=\left[x\right]+\left[y\right]+1$
证明：
$\because x+y=\left[x\right]+\left[y\right]+\left\{x\right\}+\left\{y\right\}$
$\therefore$当$0 \leqslant \left\{x\right\}+\left\{y\right\}<1$时，$\left[x\right]+\left[y\right]=\left[x+y\right]$
$ \;$当$1 \leqslant \left\{x\right\}+\left\{y\right\}<2$时，$\left[x\right]+\left[y\right]+1=\left[x+y\right]$

二、数论中相关的数和方程的求法

1、埃拉托斯特尼筛法（埃氏筛法）

内容

要得到自然数$n$以内的全部素数，必须把不大于$\sqrt{n}$的所有素数的倍数剔除，剩下的就是素数

程序实现

void primes(int n)
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=n;i++){
        if(v[i]) continue;
        cout<<i<<endl;
        for(int j=i;j<=n/i;j++) v[i*j]=1;
    }
}

时间复杂度

$\Theta \left(n \times \log \left(\log \left(n\right)\right)\right)$

时间复杂度证明

$\Theta \left(\log \left(n\right)\right)=\Theta \left(\ln \left(n\right)\right)=\Theta \left(\int_{1}^{n+1} \frac{dx}{x}\right)=\Theta \left(\sum \limits_{i=1}^{n} \int_{i}^{i+1} \frac{dx}{x}\right) < \Theta \left(\sum \limits_{i=1}^{n} \frac{1}{i}\right) \leqslant \Theta \left(\prod \limits_{质数p \leqslant n} \left(1+\frac{1}{p}\right) \times \sum \limits_{k=1}^{n} \frac{1}{k^{2}}\right) < \Theta \left(\prod \limits_{质数p \leqslant n} \left(1+\frac{1}{p}\right) \times \left(1+\sum \limits_{k=2}^{n} \left(\frac{1}{k-\frac{1}{2}}-\frac{1}{k+\frac{1}{2}} \right) \right) \right) = \Theta \left(\prod \limits_{质数p \leqslant n} \left(1+\frac{1}{p}\right) \times \left(1+\frac{2}{3}+\frac{1}{n+\frac{1}{2}}\right)\right) < \Theta \left(\frac{5}{3}\prod \limits_{质数p \leqslant n} \left(1+\frac{1}{p}\right)\right) < \Theta \left(\frac{5}{3} \prod \limits_{质数p \leqslant n} \exp \left(\frac{1}{p}\right)\right) = \Theta \left(\frac{5}{3} \exp \left(\sum \limits_{质数p \leqslant n} \frac{1}{p}\right)\right)$
$\therefore \Theta \left(n \times \log \left(\log \left(n\right)\right)\right) = \Theta \left(n \times \ln \left(\ln \left(n\right)\right)\right) < \Theta \left(n \times \ln \left(\frac{5}{3} \exp \left(\sum \limits_{质数p \leqslant n} \frac{1}{p}\right)\right)\right) = \Theta \left(n \times \sum \limits_{质数p \leqslant n} \frac{1}{p}\right)$

2、欧拉筛法

内容

在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的

程序实现

void primes(int n)
{
    memset(v,0,sizeof(v));
    m=0;
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            v[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j<=m;j++){
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
        }
    }
    for(int i=1;i<=m;i++) cout<<prime[i]<<endl;
}

时间复杂度

$\Theta \left(n\right)$

3、质因数分解

内容

$\forall N \in Z^{+} \setminus \left\{1\right\}$，把$N$化为$\prod \limits^{m}_{i=1} p^{c_{i}}_{i}$的过程叫质因数分解

程序实现

void divide(int n){
  m=0;
  for(int i=2;i*i<=n;i++) if(n%i==0){
    p[++m]=i,c[m]=0;
    while(n%i==0) n/=i,c[m]++;
  }
  if(n>1) p[++m]=n,c[m]=1;
  for(int i=1;i<=m;i++) cout<<p[i]<<'^'<<c[i]<<endl;
}

时间复杂度

$\Theta \left(\sqrt N\right)$

4、欧几里得算法（辗转相除法）

内容

$\forall a,b \in N,b \ne 0,gcd(a,b)=gcd(b,a \% b)$

证明

若$a<b$，则$gcd(b,a \% b)=gcd(b,a)=gcd(a,b)$，命题成立
若$a \geqslant b$，设$a=q \times b+r,0 \leqslant r<b,a,b$的一个公约数为$d$
$d \mid a,d \mid qb$
$\therefore d \mid \left(a-qb\right)$
$\therefore d \mid r$
$\therefore d$也是$b,r$的公约数
$\therefore a,b$的公约数集合与$b,r$的公约数集合相同
$\therefore a,b$和$b,r$的最大公约数相等

程序实现

递归写法

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

非递归写法

int gcd(int a,int b)
{
  while(b!=0){
    int temp=a;
    a=b;
    b=temp%a;
  }
  return a;
}

时间复杂度

$\Theta \left(\log \left(a+b\right)\right)$

5、扩展欧几里得算法

内容

求方程$ax+by=gcd\left(a,b\right),a,b,x,y \in Z$的解$x,y$
当$b=0$时，$x=1,y=0$为方程的解
当$b>0$时，$gcd \left(a,b\right)=gcd \left(b,a\%b\right)$
设$bx’+\left(a\%b\right)y’=gcd\left(b,a\%b\right),x’,y’ \in Z$
$\therefore bx’+\left(a\%b\right)y’=bx’+\left(a-b \left \lfloor \frac{a}{b} \right \rfloor\right)y’=ay’+b \left(x’-\left \lfloor \frac{a}{b} \right \rfloor y’\right)$
$\therefore \begin{cases} x=y’ \\y=x’-\left \lfloor \frac{a}{b} \right \rfloor y \end{cases}$

程序实现

int exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1,y=0;return a;}
    int d=exgcd(b,a%b,x,y),z=x;
    x=y,y=z-y*(a/b);
    return d;
}

6、线性同余方程组的解法

内容

设$m_{1},m_{2},\cdots \cdots,m_{n} \in Z^{+}$，对于任意$n$个整数$a_{1},a_{2},\cdots \cdots,a_{n}$，求方程组$\begin{cases} x \equiv a_{1} \pmod{m_{1}}\\x \equiv a_{2} \pmod{m_{2}}\\ \vdots\\x \equiv a_{n} \pmod{m_{n}} \end{cases}$的解

证明

设前$k-1$个方程的解为$x,m= \sum \limits^{t-1}_{i=1}m_{i},tm \equiv a_{k}-x \pmod{m_{k}}$
$\therefore x+tm \equiv a^{k} \pmod{m^{k}}$
$\therefore x’=x+tm$为前$k$个方程的解

程序实现

long long n,m[20],a[20];
long long exgcd(long long a,long long b,long long &x,long long &y)
{
  if(!b){x=1,y=0;return a;}
  long long d=exgcd(b,a%b,x,y),z=x;
  x=y,y=z-y*(a/b);
  return d;
}
long long xxtyfcz()
{
  long long M,A,d,x,y;
  M=m[1];
  A=a[1];
  for(int i=2;i<=n;i++){
    d=exgcd(M,m[i],x,y);
    if((a[i]-A)%d!=0) break;
    long long temp=abs(m[i]/d);
    x=x*((a[i]-A)/d);
    x=(x%temp+temp)%temp;
    A=M*x+A;
    M=M*m[i]/d;
  }
  return (A%M+M)%M;
}

三、例题

1、POJ2689 Prime Distance题解

题目

题目描述

原题

英文题目

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by $1$ and itself). The first prime numbers are $2,3,5,7$ but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, $2,3$ are the only adjacent primes that are also adjacent numbers.
Your program is given $2$ numbers: $L$ and $U$ ($1 \leqslant L< U \leqslant 2,147,483,647$), and you are to find the two adjacent primes $C1$ and $C2$ ($L \leqslant C1< C2 \leqslant U$) that are closest (i.e. $C2-C1$ is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes $D1$ and $D2$ ($L \leqslant D1< D2 \leqslant U$) where $D1$ and $D2$ are as distant from each other as possible (again choosing the first pair if there is a tie).

中文题意

给定两个整数$L,R$($1 \leqslant L< R \leqslant 2,147,483,647$)，求闭区间 $\left[L,R\right]$中相邻两个质数的差的最小值和最大值是多少，分别输出这两对质数

输入输出格式

输入格式

每行两个整数$L,R$($1 \leqslant L< R \leqslant 2,147,483,647,R-L \leqslant 10^6$)

输出格式

对于每个$L,R$，输出最小值和最大值，格式参照样例
若区间内无质数，输出”There are no adjacent primes.”

输入输出样例

输入样例

2 17
14 17

输出样例

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

题解

由于$L,R$的范围很大，所以埃氏筛法和欧拉筛法都无法生成$\left[1,R\right]$的所有质数
但是$R-L$的范围很小且任何一个合数$n$一定包含一个不超过$\sqrt{n}$的质因子，所以我们只需要用筛法求出$2,3,\cdots,\sqrt{n}$的所有质数
而对于每一个质数$p$，标记$i \times p \left(\left\lceil\frac{L}{p}\right\rceil \leqslant i \leqslant \left\lceil\frac{R}{p}\right\rceil\right)$为合数
标记完后，剩下的所有数就是$\left[L,R\right]$中的质数了
再两两比较，找出差最大和最小的就可以了，时间复杂度$\Theta(\sqrt{R}lnln\sqrt{R}+(R-L)lnlnR)$

2、洛谷P1072 Hankson的趣味题

题目

题目描述

原题
Hanks博士是 BT(Bio-Tech，生物技术)领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数$c_1$和$c_2$的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数$a_0,a_1,b_0,b_1$，设某未知正整数$x$满足：
1.$x$和 $a_0$的最大公约数是$a_1$；
2.$x$和$b_0$的最小公倍数是$b_1$。
Hankson的“逆问题”就是求出满足条件的正整数$x$。但稍加思索之后，他发现这样的$x$并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的$x$的个数。请你帮助他编程求解这个问题。

输入输出格式

输入格式

第一行为一个正整数$n$，表示有$n$组输入数据。接下来的$n$行每行一组输入数据，为四个正整数 $a_0,a_1,b_0,b_1$，每两个整数之间用一个空格隔开。输入数据保证$a_0$能被$a_1$整除，$b_1$能被$b_0$整除。

输出格式

共$n$行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的$x$，请输出$0$；
若存在这样的$x$，请输出满足条件的$x$的个数；

输入输出样例

输入样例

2
41 1 96 288
95 1 37 1776

输出样例

6
2

题解

因为$x$是$b_1$的约数，所以$x$的质因子一定也是$b_1$的质因子，所以我对于$b_1$的每个质因子$p$，我们可以计算$x$中有多少个$p$
假设$a_0,a_1,b_0,b_1,x$中分别有$m_{a_0},m_{a_1},m_{b_0},m_{b_1},m_x$个质因子$p$
由于$gcd(a_0,x)=b_0$，所以有$3$种情况：

若$m_{a_0}>m_{b_0}$，则$m_x=m_{b_0}$
若$m_{a_0}=m_{b_0}$，则$m_x\geqslant m_{b_0}$
若$m_{a_0}<m_{b_0}$，则$m_x$无解

同理，由于$lcm(a_1,x)=b_1$，所以有$3$种情况：

若$m_{a_1}<m_{b_1}$，则$m_x=m_{b_1}$
若$m_{a_1}=m_{b_1}$，则$m_x\leqslant m_{b_1}$
若$m_{a_1}>m_{b_1}$，则$m_x$无解

综合以上所有情况，我们可以得出共有$5$种情况：

若$m_{a_0}>m_{b_0},m_{a_1}<m_{b_1},m_{b_0}=m_{b_1}$，则$m_x=m_{b_0}=m_{b_1}$
若$m_{a_0}>m_{b_0},m_{a_1}=m_{b_1},m_{b_0}\leqslant m_{b_1}$，则$m_x=m_{b_0}$
若$m_{a_0}=m_{b_0},m_{a_1}<m_{b_1},m_{b_0}\leqslant m_{b_1}$，则$m_x=m_{b_1}$
若$m_{a_0}=m_{b_0},m_{a_1}=m_{b_1},m_{b_0}\leqslant m_{b_1}$，则$m_{b_0}\leqslant m_x\leqslant m_{b_1}$
若其他情况，则$m_x$均无解

我们将$m_x$的取法记为$sum_p$，则$x$的数量为$\prod\limits_{\text{质数}p|d}sum_p$，时间复杂度$\Theta\left(\frac{n\sqrt{d}}{lnd}\right)$

POJ3696 The Luckiest number

题目

题目描述

原题

英文题目

Chinese people think of ‘$8$’ as the lucky digit. Bob also likes digit ‘$8$’. Moreover, Bob has his own lucky number $L$. Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of $L$ and consist of only digit ‘$8$’.

中文题意

给定一个正整数$L$($L\leqslant 2\times10^9$)
问至少有多少个$8$连在一起组成的正整数是$L$的倍数

输入输出格式

输入格式

每行一个正整数$L$($L\leqslant 2\times10^9$)

输出格式

对于每个$L$，输出至少有多少个$8$连在一起组成的正整数是$L$的倍数，格式参照样例。若不存在，输出$0$

输入输出样例

输入样例

8
11
16
0

输出样例

Case 1: 1
Case 2: 2
Case 3: 0

题解

$n$个$8$连在一起组成的正整数可以记为$\frac{8}{9}(10^x-1)$
所以题目就转化为求最小的$x$使得$L|\frac{8}{9}(10^x-1)$
设$d=gcd(L,8)$
$L|\frac{8}{9}(10^x-1)\iff9L|8(10^x-1)\iff\frac{9L}{d}|10^x-1\iff10^x\equiv1\pmod{\frac{9L}{d}}$
这题的关键在于一个结论：若正整数$a,n$互质，则满足$a^x\equiv1\pmod{n}$的最小整数$x_0$为$\varphi(n)$的约数
证明：
假设满足$a^x\equiv1\pmod{n}$的最小整数$x_0$不能整除$\varphi(n)$
设$\varphi(n)=qx_0+r(0\leqslant r<x_0)$
$\because a^{x_0}\equiv1\pmod{n}$
$\therefore a^{qx_0}\equiv1\pmod{n}$
又$\because a^{\varphi(n)}\equiv1\pmod{n}$（欧拉定理）
$\therefore a^{r}\equiv1\pmod{n}$，与$x_0$最小矛盾！
$\therefore$假设不成立，原命题成立

所以，我们只需要求出$\varphi(\frac{9L}{d})$，时间复杂度$\Theta(\sqrt{L}lnL)$

其他

数论的练习题还有很多，在这里就不一一细细分析了，推荐几道题目供大家练习

洛谷P1463反素数双倍经验：BZOJ1053
洛谷P2261余数求和双倍经验：BZOJ1257
POJ3090Visible Lattice Points这题洛谷上好像有原题，只是名字改了，有知道题号的可以跟我说
洛谷P1082同余方程
POJ2891Strange Way to Express Integers
BZOJ1257Gcd
POJ2480Longge’s problem
洛谷P1516青蛙的约会双倍经验：BZOJ1447 三倍经验！！！POJ1061
BZOJ2242计算器

参考材料：
1、《算法竞赛进阶指南》李煜东著
2、《数论初步》周春荔著
3、《简明数论》潘承洞、潘承彪著

ps:写得比较匆忙，有错误请在评论区指出，我将及时更改，谢谢！