初等数论
数论是纯粹数学的分支之一,主要研究整数的性质。
整除
定义
带余除法中商为\(0\)的特殊情况,若\(a\div b=d\ldots 0\),则称\(b\)是\(a\)的约数(因数),\(a\)是\(b\)的倍数。\(b|a\)表示\(a\)能被\(b\)整除,\(b\not|a\)表示表示\(a\)不能被\(b\)整除。
有关概念
带余除法:商必须为整数的除法,\(c\div b=a\ldots d\)时,\(c=a\times b+d\);
向下取整:不大于该数的最大的整数,数学中一般记做\(\lfloor x\rfloor\),计算机科学中一般记做\(floor(x)\);
向上取整:不小于该数的最小的整数,数学中一般记做\(\lceil x\rceil\),计算机科学中一般记做\(ceil(x)\);
性质
整除的性质:
\(a|b,b|c\Rightarrow a|c\);
\(a|c,b|c,\gcd(a,b)=1\Rightarrow ab|c\);
\(a|bc,\gcd(a,b)=1\Rightarrow a|c\);
\(p|ab\Rightarrow p|a 或 p|b\)。
取整的性质:
\(\lceil\frac ab\rceil=\lfloor\frac{a+b−1}b\rfloor\);
\(\lfloor\frac ab\rfloor=\lceil\frac{a-b+1}b\rceil\);
\(a>\lfloor\frac cb\rfloor\Leftrightarrow ab>c\);
\(a<\lceil\frac cb\rceil\Leftrightarrow ab < c\);
\(a\leq\lfloor \frac cb\rfloor\Leftrightarrow ab\leq c\);
\(a<\lfloor\frac cb\rfloor\Leftrightarrow ab < c-b+1\);
\(a\geq\lceil \frac cb\rceil\Leftrightarrow ab\geq c\);
\(a>\lceil\frac cb\rceil\Leftrightarrow ab>c+b-1\)。
最大公因数 最小公倍数
定义
最大公因数指两个或多个整数共同具有的最大因数,记做\((a_1,a_2,\ldots ,a_n)\)或\(\gcd(a_1,a_2,\ldots ,a_n)\);
最小公倍数指两个或多个整数共同具有的最小倍数,记做\(\mathrm{lcm}(a_1,a_2,\ldots ,a_n)\)。
性质
- \(\mathrm{lcm}(a,b)=\frac{ab}{\gcd(a,b)}\);
- \(\mathrm{lcm}(a_1,a_2,\ldots ,a_n)=\frac{a_1a_2\ldots a_n}{\gcd(a_1,a_2,\ldots ,a_n)^{n-1}}\)。
求解算法
更相减损术(主要用于高精度求 gcd):
\[\gcd(a,b)=\gcd(a,a-b),\gcd(2a,2b)=\gcd(a,b),\gcd(2a,b)=\gcd(a,b)\]
同余
定义
定义模运算:\(a\bmod b=a-\lfloor \frac ab \rfloor\cdot b\),即\(a\div b\)的余数。
同余:\(a\equiv b\pmod p\Leftrightarrow a\bmod p=b\bmod p\)。
性质
- \(a\equiv b\pmod m\Leftrightarrow b\equiv a\pmod m\);
- \(a\equiv b\pmod m,b\equiv c\pmod m\Rightarrow a\equiv c\pmod m\);
- \(a\equiv b\pmod m\Leftrightarrow a\pm c\equiv b\pm c\pmod m\);
- \(a\equiv b\pmod m\Leftrightarrow a\cdot c\equiv b\cdot c\pmod m\);
- \(a\equiv b\pmod m,c\equiv d\pmod m\Leftrightarrow a\cdot c\equiv b\cdot d\pmod m\);
- \(a\equiv b\pmod m\Leftrightarrow a^c\equiv b^c\pmod m\);
- \(a\equiv b\pmod m\Leftrightarrow m|(b-a)\);
- \(\gcd(k,m)=d,ka\equiv ka'\pmod m\Rightarrow a\equiv a'\pmod {\frac md}\);
- 消去律:\(\gcd(c,n)=1,ac\equiv bc\pmod n\Rightarrow a\equiv b\pmod n\)。
快速幂和快速乘法
思路
令\(b=\sum_i 2^{k_i}\),则\(a^b=a^{\sum_{i} 2^{k_i}}=\prod_{i} a^{2^{k_i}},a\cdot b=a\cdot {\sum_{i} 2^{k_i}}=\sum_{i} (a\cdot 2^{k_i})\)。
实现
1 | int qpow(int a,int b) |
1 | LL qtimes(LL a,LL b) |
类欧几里得算法
扩展欧几里得算法
素数(质数)
定义
除了\(1\)和它自身外,不能被其他自然数整除的大于\(1\)的自然数。
性质
- 素数的个数是无穷的;
- 若\(a\)为大于 \(1\)的整数,在区间\((a, 2a]\)中必存在至少一个质数;
- 若\(n\)为正整数,在\(n^2\)到\((n+1)^2\)之间至少有一个质数;
- 若\(n\)为大于\(1\)的整数,在\(n\)到\(n!\)之间至少有一个质数;
- 质数的个数公式\(\pi(n)\)约等于\(\frac{n}{\ln n}\)。
乘法逆元
中国剩余定理
素数相关定理
算术基本定理(唯一分解定理):对于任何一个大于\(1\)的自然数\(N\),如果\(N\)不为质数,那么\(N\)可以唯一分解成有限个质数的乘积\(p_1^{a_1}p_2^{a_2}p_3^{a_3}\ldots p_n^{a_n}\),其中\(p_1^{a_1}< p_2^{a_2}< p_3^{a_3}< \ldots < p_n^{a_n}\)均为质数,\(a_i\)为正整数。
威尔逊定理:\((p-1)!\equiv -1\pmod p\)成立,当且仅当\(p\)是质数。
欧拉函数 欧拉定理 扩展欧拉定理 费马小定理
剩余类与剩余系
所有与整数\(a\)模\(n\)同余的整数构成的集合叫做模\(n\)的一个剩余类,记做\([a]\),\(a\)称作剩余类\([a]\)的一个代表元。 从模\(n\)的每个剩余类中各取一个数组成的集合,叫做模\(n\)的一个完全剩余系。 从模\(n\)的每个互质剩余类中各取一个数组成的集合,叫做模\(n\)的一个简化剩余系(缩系),有\(\varphi(n)\)个元素。
素数判定
- 定义法(\(O(n)\))。
- 试除法(\(O(\sqrt n)\)): 枚举\(2\sim\sqrt n\)范围内的数,判定能否整除\(n\)。
- Miller_Rabbin 算法
整数分解(分解质因子)
- 试除法(\(O(\sqrt n)\))
- 费马因数分解: 首先将\(n\)的所有\(2\)因子提取出来,使得\(n\)是一个奇数,这时可以将\(n\)表示为\(c\cdot d\),且\(c,d\)均为整数,设\(c > d\); 设\(a=\frac{c+d}2,b=a=\frac{c-d}2\),于是\(c=a+b,d=a-b\),于是\(n=a^2-b^2\); 又根据\(a \geq \sqrt{c\cdot d}=\sqrt n\),我们可以枚举大于\(n\)的完全平方数\(a\),判断\(a^2-n\)是否为完全平方数,求出\(c,d\)然后递归分解即可。
- Pollard_rho 算法
素数筛
阶和原根
阶
定义
若\((a,p)=1,p > 1\),使得\(a^x\equiv 1\pmod p\)成立的最小正整数\(x\)称为\(a\)模\(p\)的阶,记为\(\delta_pa\)。
性质
- 若\((a,p)=1,p > 0\),那么正整数\(x\)是同余式\(a^x\equiv 1\pmod p\)的一个解当且仅当\(\delta_pa|x\);
- 若\((a,p)=1,p > 0\),则\(\delta_pa|\varphi(p)\);
- 若\((a,p)=1,p > 0\),那么正整数\(a^i\equiv a^j\pmod p\),当且仅当\(i\equiv j\pmod {\delta_pa}\),其中\(i,j \geq 0\);
- \(\delta_p{(a^k)}=\frac{\delta_pa}{(\delta_pa,k)}\);
- \((\delta_pa,k)=1\)时,\(\delta_p{(a^k)}=\delta_pa\)。
求解算法
暴力枚举\(\varphi(p)\)的因数。
原根
定义
满足\(\delta_pa=\varphi(p)\)的\(a\)称为模\(p\)的原根。
性质
- 只有\(2,4,p^k,2p^k\)存在原根,其中\(p\)为奇质数,\(k\)为任意自然数;
- 当正整数\(p\)存在原根时,它就有\(\varphi(\varphi(p))\)个原根;
- 若\((a,p)=1,p > 0\),如果\(a\)是模\(p\)的一个原根,则\(a^0,a^1,\ldots,a^{\varphi(p)-1}\)模\(p\)两两不同余,即\(\{a^0,a^1,\ldots,a^{\varphi(p)-1}\}\)构成模\(p\)的缩系;
- 如果\(a\)是模\(p\)的原根,那么\(a^{p-1}\equiv 1\pmod p\)当且仅当指数为\(p-1\)的时候成立(\(p\)是素数);
求解算法
求模\(p\)的原根\(a\):
从小到大枚举\(a\),判断是否为原根:
令\(\varphi(p)=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}\),若恒有\(a^{\frac{\varphi(p)}{p_i}}\not=1\pmod p\),则\(a\)是模\(p\)的原根。
证明:
如果\(a\)不是模\(p\)的原根,那么存在\(t < \varphi(p)\)使得\(a^t\equiv 1\pmod p\);
根据裴蜀定理,一定存在一组\(k,r\)使得\(kt+r\varphi(p)=gcd(t,\varphi(p))\);
于是:
\[\begin{align}1 & \equiv a^t \\ & \equiv a^{kt} \\ & \equiv a^{gcd(t,\varphi(p))-r\varphi(p)}\\ & \equiv a^{gcd(t,\varphi(p))}\pmod p\end{align}\]
又\(t < p-1\),于是\(gcd(t,\varphi(p)) < p-1\);
又\(gcd(t,\varphi(p)) | p-1\),故\(gcd(t,\varphi(p))\)至少整除\(\frac{\varphi(p)}{p_1},\frac{\varphi(p)}{p_2},\ldots,\frac{\varphi(p)}{p_k}\)其中之一,假设\(gcd(t,\varphi(p))|\frac{\varphi(p)}{p_i}\);
于是\(a^{\frac{\varphi(p)}{p_i}}\equiv {a^{gcd(t,\varphi(p))}}^s\equiv 1^s\equiv 1\pmod p\)。
二次剩余
BSGS exBSGS
数论函数(算术函数)
定义
指定义域为正整数、陪域为复数的函数。
有关概念
积性函数:有如下性质的,定义域为正整数的数论函数:\(f(1)=1\),且当\(a\)和\(b\)互质时,\(f(ab)=f(a)f(b)\),若对于任意\(a,b\)都满足上述性质,则称其为完全积性函数;
狄利克雷卷积:设\(f\),\(g\)是两个数论函数,则卷积运算\(f\ast g\)定义为: \[(f\ast g)(n) = \sum_{d|n}{f(d)g(\frac nd)}\]
卷积运算满足:
交换律:\(f\ast g=g\ast f\);
结合律:\((f\ast g)\ast h=f\ast(g\ast h)\)。
分配律:\(f\ast (g+h)=f\ast g+f\ast h=(g+h)\ast f\)
举例
- \(\varphi(n)\),欧拉函数;
- \(e(n)\),元函数,定义为\(e(n)=[n=1]\);
- \(1(n)\) ,不变的函数,定义为\(1(n)=1\)(完全积性);
- \(Id(n)\),单位函数,定义为\(Id(n)=n\)(完全积性);
- \(d(n)\),\(n\)的因数个数,定义为\(d(n)=\sum_{d|n} 1\);
- \(\varepsilon(n)\),狄利克雷卷积单位元,定义为\(\varepsilon(n)=\begin{cases}1,\quad n=1\\0,\quad n\not=1\end{cases}\)(完全积性); 易得:\((\varepsilon\ast f)(n) = \sum_{ij=n} \varepsilon(i)f(j)\),即\(\varepsilon\ast f=f\);
- \(gcd(n,k)\),最大公因数,当\(k\)固定的情况;
- \(\sigma(n)\),\(n\)的正因子之和,定义为\(\sigma(n)=\sum_{d|n} d\);
- \(\sigma_k(n)\),除数函数,定义为\(\sigma_k(n)=\sum_{d|n} d^k\);
- \((\frac np)\),勒让德符号,当\(p\)是固定质数的情况(完全积性);
- \(\mu(n)\),莫比乌斯函数。
性质
如果\(f(n),g(n)\)是积性函数,那么下列函数也是积性函数:
- \(h(n)=f(n^k)\);
- \(h(n)=f^k(n)\);
- \(h(n)=f(n)g(n)\);
- \(h(n)=\sum_{d|n} f(d)g(\frac nd)\)。