初等数论

数论是纯粹数学的分支之一，主要研究整数的性质。

整除

定义

带余除法中商为\(0\)的特殊情况，若\(a\div b=d\ldots 0\)，则称\(b\)是\(a\)的约数（因数），\(a\)是\(b\)的倍数。\(b|a\)表示\(a\)能被\(b\)整除，\(b\not|a\)表示表示\(a\)不能被\(b\)整除。

有关概念

1. 带余除法：商必须为整数的除法，\(c\div b=a\ldots d\)时，\(c=a\times b+d\)；

2. 向下取整：不大于该数的最大的整数，数学中一般记做\(\lfloor x\rfloor\)，计算机科学中一般记做\(floor(x)\)；

3. 向上取整：不小于该数的最小的整数，数学中一般记做\(\lceil x\rceil\)，计算机科学中一般记做\(ceil(x)\)；

性质

1. 整除的性质：

   1. \(a|b,b|c\Rightarrow a|c\)；

   2. \(a|c,b|c,\gcd(a,b)=1\Rightarrow ab|c\)；

   3. \(a|bc,\gcd(a,b)=1\Rightarrow a|c\)；

   4. \(p|ab\Rightarrow p|a 或 p|b\)。

2. 取整的性质：

   1. \(\lceil\frac ab\rceil=\lfloor\frac{a+b−1}b\rfloor\)；

   2. \(\lfloor\frac ab\rfloor=\lceil\frac{a-b+1}b\rceil\)；

   3. \(a>\lfloor\frac cb\rfloor\Leftrightarrow ab>c\)；

   4. \(a<\lceil\frac cb\rceil\Leftrightarrow ab < c\)；

   5. \(a\leq\lfloor \frac cb\rfloor\Leftrightarrow ab\leq c\)；

   6. \(a<\lfloor\frac cb\rfloor\Leftrightarrow ab < c-b+1\)；

   7. \(a\geq\lceil \frac cb\rceil\Leftrightarrow ab\geq c\)；

   8. \(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)\)。

性质

1. \(\mathrm{lcm}(a,b)=\frac{ab}{\gcd(a,b)}\)；
2. \(\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}}\)。

求解算法

1. 欧几里得算法

2. 更相减损术（主要用于高精度求 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\)。

性质

1. \(a\equiv b\pmod m\Leftrightarrow b\equiv a\pmod m\)；
2. \(a\equiv b\pmod m,b\equiv c\pmod m\Rightarrow a\equiv c\pmod m\)；
3. \(a\equiv b\pmod m\Leftrightarrow a\pm c\equiv b\pm c\pmod m\)；
4. \(a\equiv b\pmod m\Leftrightarrow a\cdot c\equiv b\cdot c\pmod m\)；
5. \(a\equiv b\pmod m,c\equiv d\pmod m\Leftrightarrow a\cdot c\equiv b\cdot d\pmod m\)；
6. \(a\equiv b\pmod m\Leftrightarrow a^c\equiv b^c\pmod m\)；
7. \(a\equiv b\pmod m\Leftrightarrow m|(b-a)\)；
8. \(\gcd(k,m)=d,ka\equiv ka'\pmod m\Rightarrow a\equiv a'\pmod {\frac md}\)；
9. 消去律：\(\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})\)。

实现

int qpow(int a,int b)
{
    int ans=1;
    for(;b;b>>=1,a=a*a%MOD)
        if(b&1)ans=ans*a%MOD;
    return ans;
}

LL qtimes(LL a,LL b)
{
    LL ans=1;
    for(;b;b>>=1,a=a+a%MOD)
        if(b&1)ans=ans+a%MOD;
    return ans;
}

类欧几里得算法

类欧几里得算法

扩展欧几里得算法

扩展欧几里得算法

素数（质数）

定义

除了\(1\)和它自身外，不能被其他自然数整除的大于\(1\)的自然数。

性质

1. 素数的个数是无穷的；
2. 若\(a\)为大于 \(1\)的整数，在区间\((a, 2a]\)中必存在至少一个质数；
3. 若\(n\)为正整数，在\(n^2\)到\((n+1)^2\)之间至少有一个质数；
4. 若\(n\)为大于\(1\)的整数，在\(n\)到\(n!\)之间至少有一个质数；
5. 质数的个数公式\(\pi(n)\)约等于\(\frac{n}{\ln n}\)。

乘法逆元

乘法逆元

中国剩余定理

中国剩余定理

素数相关定理

1. 算术基本定理（唯一分解定理）：对于任何一个大于\(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\)为正整数。

2. 威尔逊定理：\((p-1)!\equiv -1\pmod p\)成立，当且仅当\(p\)是质数。

欧拉函数 欧拉定理 扩展欧拉定理 费马小定理

欧拉函数

剩余类与剩余系

所有与整数\(a\)模\(n\)同余的整数构成的集合叫做模\(n\)的一个剩余类，记做\([a]\)，\(a\)称作剩余类\([a]\)的一个代表元。 从模\(n\)的每个剩余类中各取一个数组成的集合，叫做模\(n\)的一个完全剩余系。 从模\(n\)的每个互质剩余类中各取一个数组成的集合，叫做模\(n\)的一个简化剩余系（缩系），有\(\varphi(n)\)个元素。

素数判定

1. 定义法（\(O(n)\)）。
2. 试除法（\(O(\sqrt n)\)）： 枚举\(2\sim\sqrt n\)范围内的数，判定能否整除\(n\)。
3. Miller-Rabin 算法

整数分解（分解质因子）

1. 试除法（\(O(\sqrt n)\)）
2. 费马因数分解： 首先将\(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\)然后递归分解即可。
3. Pollard Rho 算法

素数筛

素数筛

阶和原根

阶

定义

若\((a,p)=1,p > 1\)，使得\(a^x\equiv 1\pmod p\)成立的最小正整数\(x\)称为\(a\)模\(p\)的阶，记为\(\delta_pa\)。

性质

1. 若\((a,p)=1,p > 0\)，那么正整数\(x\)是同余式\(a^x\equiv 1\pmod p\)的一个解当且仅当\(\delta_pa|x\)；
2. 若\((a,p)=1,p > 0\)，则\(\delta_pa|\varphi(p)\)；
3. 若\((a,p)=1,p > 0\)，那么正整数\(a^i\equiv a^j\pmod p\)，当且仅当\(i\equiv j\pmod {\delta_pa}\)，其中\(i,j \geq 0\)；
4. \(\delta_p{(a^k)}=\frac{\delta_pa}{(\delta_pa,k)}\)；
5. \((\delta_pa,k)=1\)时，\(\delta_p{(a^k)}=\delta_pa\)。

求解算法

暴力枚举\(\varphi(p)\)的因数。

原根

定义

满足\(\delta_pa=\varphi(p)\)的\(a\)称为模\(p\)的原根。

性质

1. 只有\(2,4,p^k,2p^k\)存在原根，其中\(p\)为奇质数，\(k\)为任意自然数；
2. 当正整数\(p\)存在原根时，它就有\(\varphi(\varphi(p))\)个原根；
3. 若\((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\)的缩系；
4. 如果\(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

BSGS 算法

数论函数（算术函数）

定义

指定义域为正整数、陪域为复数的函数。

有关概念

1. 积性函数：有如下性质的，定义域为正整数的数论函数：\(f(1)=1\)，且当\(a\)和\(b\)互质时，\(f(ab)=f(a)f(b)\)，若对于任意\(a,b\)都满足上述性质，则称其为完全积性函数；

2. 狄利克雷卷积：设\(f\),\(g\)是两个数论函数，则卷积运算\(f\ast g\)定义为： \[(f\ast g)(n) = \sum_{d|n}{f(d)g(\frac nd)}\]

   卷积运算满足：

   1. 交换律：\(f\ast g=g\ast f\)；

   2. 结合律：\((f\ast g)\ast h=f\ast(g\ast h)\)。

   3. 分配律：\(f\ast (g+h)=f\ast g+f\ast h=(g+h)\ast f\)

举例

1. \(\varphi(n)\)，欧拉函数；
2. \(e(n)\)，元函数，定义为\(e(n)=[n=1]\)；
3. \(1(n)\) ，不变的函数，定义为\(1(n)=1\)（完全积性）；
4. \(Id(n)\)，单位函数，定义为\(Id(n)=n\)（完全积性）；
5. \(d(n)\)，\(n\)的因数个数，定义为\(d(n)=\sum_{d|n} 1\)；
6. \(\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\)；
7. \(gcd(n,k)\)，最大公因数，当\(k\)固定的情况；
8. \(\sigma(n)\)，\(n\)的正因子之和，定义为\(\sigma(n)=\sum_{d|n} d\)；
9. \(\sigma_k(n)\)，除数函数，定义为\(\sigma_k(n)=\sum_{d|n} d^k\)；
10. \((\frac np)\)，勒让德符号，当\(p\)是固定质数的情况（完全积性）；
11. \(\mu(n)\)，莫比乌斯函数。

性质

如果\(f(n),g(n)\)是积性函数，那么下列函数也是积性函数：

1. \(h(n)=f(n^k)\)；
2. \(h(n)=f^k(n)\)；
3. \(h(n)=f(n)g(n)\)；
4. \(h(n)=\sum_{d|n} f(d)g(\frac nd)\)。

莫比乌斯函数 莫比乌斯反演

莫比乌斯函数及莫比乌斯反演

线性筛

线性筛