整除

定义

设$a,b \in \mathbb{Z}$，如果存在$q \in \mathbb{Z}$，使得$b=aq$，那么就可以说$b$可以被$a$整除，记作$a \mid b$，且称$b$是$a$的倍数，$a$是$b$的约数（因数、除数）

性质

• $a \mid b \Longleftrightarrow -a \mid b \Longleftrightarrow a \mid b \Longleftrightarrow \lvert a \rvert \mid \lvert b \rvert$
• $a \mid b,b \mid c \Longrightarrow a \mid c$
• $a \mid b,a \mid c \Longleftrightarrow \forall x,y \in \mathbb{Z},a \mid bx + cy$
• $a \mid b,m \neq 0 \Longleftrightarrow ma \mid mb$
• $a \mid b,b \mid a \Longrightarrow b= \pm a$
• $a \mid b,b \neq 0 \Longrightarrow \lvert a \rvert \le \lvert b \rvert$

• 设$a \neq 0,b = qa+c$

  那么$a \mid b \Longleftrightarrow a \mid c$

• 欧几里得引理：若质数$p \mid ab$，则不是$p \mid a$，就是$p \mid b$

算数基本定理（唯一分解定理）

定义

任何一个大于$1$的自然数$N$，如果$N$不是质数，那么$N$可以唯一分解成有限个质数的乘积。

即：

$$N=p_1^{a_31} \times p_2^{a_2} \times p_3^{a_3} \times \cdots \times p_k^{a_k}$$

或：

$$\forall \in \mathbb{N},A>1 \quad \exists \prod^n_{i=1}p_i^{a_i}=A$$

这里$p_1 \lt p_2 \lt p_3 \lt \cdots \lt p_n$且均为质数，且表示的方法是唯一的。这样的分解成为$N$的标准分解式。

证明

存在性

假设存在大于$1$的自然数不能写成质数的乘积，把最小的那个称为$n$。自然数可以根据其可除性（是否能表示成两个不是自身的自然数的乘积）分成三类：质数、合数和$1$。

首先，按照定义，$n$大于$1$。其次，$n$不是质数，因为质数$p$可以写成质数乘积：$p=p$，这与假设不相符合。因此，$n$只能是合数，但每个合数都可以分解成两个严格小于自身而大于$1$ 的自然数的积。

设$n=a \times b$，其中$a$和$b$都是介于$1$和$n$之间的自然数，因此，按照$n$的定义，由于$n$是大于$1$的自然数而不能写成质数的乘积中最小的数，$a$和$b$都可以写成质数的乘积。从而$n=a×b$也可以写成质数的乘积。

由此产生矛盾。因此大于$1$的自然数必可写成质数的乘积。

唯一性

假设有些大于$1$的自然数可以以多于一种的方式写成多个质数的乘积，那么假设$n$是其中最小的一个。

首先$n$不是质数。将$n$用两种方法写出：$n=p_1p_2p_3 \cdots p_r=q_1q_2q_3 \cdots q_s$。根据欧几里得引理，质数$p_1 \mid q_1q_2q_3 \cdots q_s$，所以 $q_1,q_2,q_3 \cdots q_s$ 中有一个能被$p_1$整除，不妨设为 $q_1$。但$q_1$也是质数，因此$q_1=p_1$。所以，比$n$小的正整数$n^{'}=p_2p_3⋯p_r$也可以写成$q_2q_3 \cdots q_s$。

这与$n$的最小性矛盾，因此唯一性得证。

推论

• 求一个数$x$约数的个数$d(n)=\prod^k_{i=1}(a_i+1)$（符号意义与上文相同）

质数（素数）

定义

质数素数即，是指在大于$1$的自然数中，除了$1$和它本身以外不再有其他因数的自然数。否则这个数是合数。

相关定理

素数定理

在数论中，素数定理描述素数在自然数中分布的渐进情况，随着数字的增大，素数的密度逐渐降低。对于正实数$x$，定义$\pi (x)$为素数计数函数，亦即不大于$x$的素数个数。我们可以大概的估计：

$$\pi(x) \approx \frac{x}{\ln x}$$

更好地估计为：

$$\pi(x)=Li(x)+O(xe^{-\frac{1}{15}\sqrt{\ln x}})$$

其中：$Li(x)=\int^x_2 \frac{dt}{\ln t}$（对数积分），第二项是误差估计。

求质数

判断一个数是不是质数

从$2$枚举到$\sqrt{n}$$^①$试试是否可以整除，如果可以，就不是质数。显然时间复杂度是$O(\sqrt{n})$的。

①为什么枚举到$\sqrt{n}$ ？

一个合数一定可以表示为$a \times b$的形式，当$a \le \sqrt{n}$时，$b \ge \sqrt{n}$，如果枚举超过$\sqrt{n}$，就相当于$a$与$b$互换又算了一遍，是无作用的，所以只需要枚举到$\sqrt{n}$。

筛法

顾名思义，筛就是把不是质数的数去掉。我们用数组$flag[]$表示某个数是不是质数，数组值默认为$false$表示默认都是质数，$true$表示是合数，然后从$2$开始枚举$i$到要筛的上限$M$，如果，flag[i]==false就加入质数数组$prime[]$然后枚举所有已求的质数$prime[j]$，让$flag[i \times prime[j]]=true$这样保证所有合数都被筛掉了，因为对于任意合数$a$，总能表示成$a=i \times prime[j]$且$i \ge prime[j]$$^②$，直接取最小的质因子就能做到这一点，不过效率不太行，时间复杂度为$O(n \log \log n)$，因为如果$a=k \times p \times q$，其中$k \times p \ge q$且$k \times q \ge p$的话，那么$a$被筛了两次。

那我们只需要当i%prime[j]==0时立刻break，也就是$i$只乘到小于它最小质因子$p_0$。令$i=k \times p_0$，如果找到了$p_0$且我们不停止，我们下一次计算会变成$i \times prime[j+1]$，可以转化为$k \times p_0 \times prime[j+1]$，而这个数的最小质因数就不是$prime[j+1]$，而是$prime[j]$因为$p_0<prime[j+1]$，所以对于这个数，我们可以让$i$枚举到$k \times prime[j+1]$时，与$prime[j]$这个最小质因数相乘而筛去，否则就会把一个数筛好几遍。

②为什么对于任意合数$a$，总能表示成$a=i \times prime[j]$且$i \ge prime[j]$？

证明方法与①相同，一个大于$\sqrt{n}$的质数乘上任意一个数都不会等于$n$（$n \neq 0$，$n$为合数），只有小于$\sqrt{n}$的数才能与另一个数相乘得到$n$，而另一个数一定大于$\sqrt{n}$，所以得出如上结论。

for(int i=2;i<=n;i++){
    if(!flag[i]) prime[++cnt]=i;//flag[i]表示i是否为被筛过，prime数组是质数表，cnt是质数数量
    for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
        flag[i*prime[j]]=1;
        if(i%prime[j]==0)//关键措施
            break;
    }
}

for(int i=2;i<=n;i++){//除了筛质数，还可以记录每一个数它的最小质因数
    if(!flag[i]) prime[++cnt]=i,flag[i]=i;
    for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
        flag[i*prime[j]]=prime[j];
        if(i%prime[j]==0)
            break;
    }
}

欧拉函数

前置知识

• 模$m$后余数相同的所有数组成的集合叫模$m$的同余类。比如模$10$为$1$的同余类$A_1=\{1,11,21,\ldots \}$。
• 从模$m$的$m$个同余类$A_0,A_1,\ldots,A_{m-1}$中，每个类$A_i$任意挑出一个数$a_i$，组成一个集合叫做模$m$的完全剩余系。
• 从完全剩余系中取出和$m$互质的数组成一个集合叫模$m$的既约剩余系，也叫缩系。
• 缩系的大小就叫做欧拉函数，定义为$\varphi(m)$，有时也写作$phi(m)$。

定义

对正整数n，欧拉函数是小于$n$的正整数中与$n$互质的数的数目。

[alert]注意互质的定义，是指两个数的最大公因数为$1$，所以$1$和任何正整数互质。[/alert]

性质

• 如果$p$是质数，那么$\varphi(p)=p-1$。
• 如果$n$是一个质数的某一次方，即$n=p^k$（p为质数，$k\in \mathbb{N_+}$），则$\varphi(p^k)=p^k-p^{k-1}=p^k(1-\frac1p)$。
• 如果$m_1$与$m_2$互质，那么$\varphi(m_1 \times m_2)=\varphi(m_1)\times \varphi(m_2)$。
• 如果$m_1,m_2$有相同的质因数，那么$\varphi(m_1*m_2)=m_1 \times \varphi(m_2)$。

• 设$n=p^{k_1}_1\times p^{k_2}_2 \times p^{k_3}_3 \times \cdots \times p^{k_r}_r$，那么：

  $\begin{equation}\begin{split}\varphi(n)&=\varphi(p_1^{k_1})\times\varphi(p_2^{k_2})\times\varphi(p_3^{k_3})\cdots\times \varphi(p_r^{k_r})\\&=p_1^{k_1}\times p_2^{k_2}\times p_3^{k_3}\times\cdots\times p_r^{k_r}\times(1-\frac1{p_1})(1-\frac1{p_2})(1-\frac1{p_3})\cdots(1-\frac1{p_r})\end{split}\end{equation}$

  最后得出欧拉函数通用计算公式：$\varphi(n)=n(1-\frac{1}{p_1})(1-\frac1{p_2})(1-\frac1{p_3})\cdots(1-\frac1{p_r})$。

• 设$m,n\in \mathbb{N^+}$，且$\gcd(a,m)=1$，则我们有：

  $a^{\varphi(m)}\equiv1(\bmod n)$

  当$m\in\{素数\}$时该结论加强为费马小定理。

求欧拉函数

直接枚举从$1$到$n$的数判断是否和$n$互质也是可以的，但是我们一般用线性筛求出$1$到$n$的所有欧拉函数值。

在筛质数的时候，对于一个合数，它要么被i*prime[j] (i%prime[j]==0)，要么被i*prime[j] (i%prime[j]!=0)。设数组$phi[i]$表示$\varphi(i)$，可以得到：

1. 对于第一种情况：phi[i*prime[j]]=phi[i]*primj[j]。
2. 对于第二种情况：phi[i*prime[j]]=phi[i]*phi[prime[j]]。

原理就是上面的第$3$、$4$条性质。

phi[1]=1;
for(int i=2;i<=n;i++){
    if(!flag[i])    prime[++cnt]=i,phi[i]=i-1;
    for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
        flag[i*prime[j]]=1;
        phi[i*prime[j]]=phi[i]*phi[prime[j]];
        if(i%prime[j]==0){
            phi[i*prime[j]]=phi[i]*prime[j];
            break;
        }
    }
}

欧几里得算法

GCD

定义

GCD即为最大公因数。在这篇文章中，求$a,b$的GCD会使用$\gcd(a,b)$表示.

求法

给出两个数$a,b$，求解$\gcd(a,b)$常用辗转相除法，也就是欧几里得算法。结论就是$\gcd(a,b)=\gcd(b,a\bmod b)$，直到最后b==0直接给出结果。在算法中我们可以用递归或循环实现。这样做很快，每次能让问题规模缩减一半$^③$。注意：当$a,b$中有个数是$0$时，$\gcd(a,b)$等于那个不为$0$的数，因为任何书都能整除$0$。

③证明：$a\bmod b\gt \frac a2$

当$b \gt \frac a2$时，

$a \bmod b \lt b\lt\frac a2$

当$b \gt \frac a2$时

$a \bmod b\lt a-b\lt \frac a2$

证明

证法$1$：

$a$可以表示成$a = kb + r$

假设$d$是$a,b$的一个公约数，记作$d\mid a,d \mid b$，即$a$和$b$都可以被$d$整除。

而$r = a - kb$，两边同时除以$d$，$\frac rd=\frac ad-\frac{kb}d$，由等式右边可知$m=\frac rd$为整数，因此$d\mid r$

因此$d$也是$b,a \bmod b$的公约数。

因$(a,b)$和$(b,a \bmod b)$的公约数相等，则其最大公约数也相等，得证。

证法$2$：

令$d=\gcd(a,b)$

则可得$a=m·d,b=n·d$

则$m·d=t·n·d+a\bmod b \Longrightarrow a \bmod b=d·(m-t·n)$

$\gcd(b,a\bmod b)=\gcd(n·d,(m-t·n)·d)$

令$\gcd(n,m-t·n)=e \Longrightarrow n=x·e,m-t·n=y·e$

则$m-x·e·n=y·e \Longrightarrow m=e·(x·n+y)$

由$\gcd(n,m)=1$知$\gcd(e·(x·n+y),e·x)=1$

故$e=1$

故$\gcd(n·d,(m-t·n)·d)=d$，即$\gcd(b,a\bmod b)=\gcd(a,b)$

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

LCM

定义

LCM即为最小公倍数。在这篇文章中，求$a,b$的LCM会使用$\rm{lcm}(a,b)$表示.。

求法

上文已经计算出了$\gcd(a,b)$，这里有一个结论：

$$\gcd(a,b)\times \rm{lcm}(a,b)=ab$$

根据这个公式可以通过GCD求出LCM。

证明

假设一个数$A$和一个数$B$有最大公因数$x$，则$A = a \times x$，$B=b\times x$。其中数字$a$和数字$b$是互质的。如果$a$和$b$不是互z质的话，可以得到更大的公因数。那么易知得到：
$A \times B = B \times A $
即：
$A\times b\times x=B\times a\times x$
公式中左右两端消除公因子x得到：
$A \times b = B \times a$
因为$a$和$b$是互质的，$A$和$B$是我们要求的最小公倍数的两个数。所以$A \times b$或者$B \times a$就是我们需要的最小公倍数。也就可以得到两个数的最小公倍数是两个数之间的乘积除于两个数之间的最大公因数。

扩展欧几里得

[alert]学习扩展欧几里得，需要先学习裴蜀定理。[/alert]

方法

对于求解一个方程$ax+by=c$，根据裴蜀定理，我们可以将其转化为$ax+by=d$，最后乘上$\frac cd$转化为原式的解。

步骤（递归）

令$ax_1+by_1=\gcd(a,b)$

$bx_2+(a\ \bmod b)·y_2=gcd(b,a\bmod b)$

由$gcd(a,b)=gcd(b,a \bmod b)$知

$\begin{equation}\begin{split}&ax_1+by_1=bx_2+(a \bmod b)·y_2\\=&bx_2+(a-b·\lfloor\frac ab \rfloor)·y_2\\=&ay_2+b·(x_2-\lfloor\frac ab\rfloor ·y_2)\end{split}\end{equation}$

故我们可以找到一组特解$x_1=y_2,y_1=(x_2-\lfloor \frac ab \rfloor ·y_2)$

如此递归到边界情况。那么边界情况是什么？

首先这是一个递归式子，当b==0

步骤（迭代）

我不会

方程的通解

对于任意一对解$x_0,x_1$，其他解可以表示为$x_0+\frac bd \times k$和$y_0-\frac ad \times k$（$k=1,-1,2,-2,\ldots$）

推导：

1. 若使$a \times (x+m)+b\times (x-n)=ax+by+am-bn=d$，那么$a\times m=b\times n$，可以得到$\frac mn=\frac ba$
2. 由于$\gcd(a,b)=d$，所以$m$和$n$最小只能取$\frac bd$和$\frac ad$。（$m$再小就找不到整数$n$使得$\frac mn=\frac ba$了，$n$同理。）

所以有时候我们要求$x \gt 0$或者要求$x,y$都大于0，就可以用这种方式调整$x$和$y$。

裴蜀定理（贝祖定理）

内容

$ax+by=c,x\in \mathbb{Z_+},y\in \mathbb{Z_+}$成立的充要条件是$gcd(a,b)\mid c$

证明

设$\gcd(x,b)=d$

令$a=nd,b=md$，则$ax+by=dnx+dmy$

根据整除性质得出：$d \mid (dnx+dmy)$

所以$d \mid (ax+by)$

即：$\gcd(a,b)\mid c$

引理

丢番图方程$ax+by=c$有解当且仅当$d \mid c$（$d=\gcd(a,b)$）

也就是说，对于任意整数$x,y$，$ax+by$的最小正值为$\gcd(a,b)$

证明

①必要性

由裴蜀定理，不存在整数$x,y$，使得$d$不整除$ax+by$

②充分性

要证$ax+by+c$有解，只要证$ax+by=d$有解

令$\forall x,y\in \mathbb{Z},ax+by$都能得到的最小正值为$x$

由裴蜀定理，$d\mid s$，则$d \le s$

令$q=\lfloor\frac qs \rfloor,p=a \bmod s$

则$p=a-q ·(ax+by)=a·(1-qx)-qby=a·(1-qx)+b·(-qy)$

由$p=a \bmod s$知$0 \le p \lt s$

又$s$为$ax+by$能得到的最小正值

故$p=0$，即$s \mid a$

同理，$s \mid b$，即$s\mid d$，故$s\ge d$

综上：$s\mid d$

即对于$\forall x,y\in \mathbb{Z},ax+by$能得到的最小正值为$d$

故$\exists x,y\in \mathbb{Z}$，使$ax+by=d$

即$\exists x,y\in \mathbb{Z}$，使$ax+by=c$

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

for(int i=1;i<=n;i++){
        read(a);
        if(a<0)
            a=-a;
        ans=gcd(ans,a);
    }

来源：洛谷：P4549 【模板】裴蜀定理

丢番图方程

定义

丢番图方程又名不定方程、整系数多项式方程，是有一个或者几个变量的整系数方程，它们的求解仅仅在整数范围内进行，最后这个限制使得丢番图方程求解与实数范围方程的求解有根本不同。丢番图方程的形式如下：

$$a_1x_1^{b_1}+a_2x_2^{b_2}+\cdots+a_nx_n^{b_n}=c$$

丢番图方程的例子有：贝祖等式（裴蜀等式）、勾股定理的整数解、四平方定理和费马最后定理等。

中国剩余定理

同余

如果$a-b$是$m$的倍数，那么我们就说$a$和$b$在模$m$的意义下同余，记为$a\equiv b(\bmod m)$。这个表达式实际上和$a\bmod b=m$是等价的，但是在数学上我们习惯用上面的形式。

一次同余方程组

同余方程就是用同余定义的方程，例如$x\equiv a(\bmod m)$。一次同余方程组就是由若干个一次同余方程组组成的方程组。例如：

$$\begin{cases}x\equiv a_1 \bmod m_1\\x=a_2 \bmod m_2\\\quad\quad\quad\cdots\\x\equiv a_k\bmod m_k\end{cases}$$

中国剩余定理主要用于求解一次同余方程组，而且要求$m_1,m_2,\ldots,m_k$互质。

内容

中国剩余定理的结论看上去非常复杂，其实把每个部分的意义拆分开后非常简单。结论如下。

设$M=m_1\times m_2\times \cdots \times m_n=\prod^n_{i=1}m_i$是整数$m_1,m_2,\ldots,m_n$的乘积，并设$M_i=\frac Mm,\forall i \in \{1,2,\ldots,n\}$是除了$m_i$以外的$n-1$个整数的乘积。 设$t_i=M_i^{-1}$为$M_i$模$m$的数论倒数（$t_i$为$M_i$模$m_i$意义下的逆元）$M_it_i\equiv 1(\bmod m_i),\forall i\in\{1,2,\ldots,n\}$。方程组的通解形式为$x=a_1t_1M_1+a_2t_2M_2+\cdots+a_nt_nM_n+kM=kM+\sum^n_{i=1}a_it_iM_i,k\in \mathbb{Z}$。在模$M$的意义下，方程组只有一个解$x=(\sum^n_{i-1}a_it_iM_i)\bmod M$。

证明

从假设可知，对任何$i\in \{1,2,\ldots,n\}$。由于$\forall j \in \{1,2,\ldots,n\},j\neq i, \gcd(m_i,m_j)=1$，所以$\gcd(m_i,M_i)=1$，这说明存在整数$t_i$使得$t_iM_i\equiv 1(\bmod m_i)$。这样的$t_i$叫做$M_i$模$m_i$的数论倒数。考察乘积$a_it_iM_i$可知：

$a_it_iM_i\equiv a_i·1\equiv a_i(\bmod m_i)$，$\forall j\in \{1,2,\ldots,n\},j\neq i,a_it_iM_i\equiv 0(\bmod 0)$。

所以$x=a_1t_1M_1+a_2t_2M_2+\cdots+a_nt_nM_n$满足：$\forall i\in \{1,2,\ldots,n\},x=a_it_iM_i+\sum_{j\neq i}a_jt_jM_j\equiv a_i+\sum_{j\neq i}0\equiv a_i(\bmod m_i)$。

这说明$x$就是方程组的一个解。

另外，假设$x_1$和$x_2$都是方程组的解，那么：

$\forall \in \{1,2,\ldots,n\},x_1-x_2\equiv 0(\bmod m_i)$。

而$m_1,m_2,\ldots,m_n$两两互质，这说明$M=\prod^n_{i=1}m_i整除x_1-x_2$，所以方程组的任何两个解必然相差$M$的整数倍。而另一方面，$x=a_1t_1M_1+a_2t_2M_2+\cdots+a_nt_nM_n$是一个解，同时所有形式为：$a_1t_1M_1+a_2t_2M_2+\cdots+a_nt_nM_n+kM=kM+\sum^n_{i=1}a_it_iM_i,k\in \mathbb{Z}$的整数也是方程组的解。所以方程组的所有解的集合就是$kM+\sum^n_{i=1}a_it_iM_i,k \in \mathbb{Z}$。