数论专题 I

[LaTeX 数学公式大全](https://www.luogu.com.cn/blog/IowaBattleship/latex-gong-shi-tai-quan) ### 简介 主要是一些数学中的基础？知识。 包含了逆元， EXGCD，CRT&EXCRT，Lucas，EXLucas，BSGS&EXBSGS，Miller Rabin&Pollard Rho，原根。 ### 【广告】 我的其他数学题单。 - [我的数论专题II](https://www.luogu.com.cn/training/236965) ### 其他题单 - [数学·同余方程](https://www.luogu.com.cn/training/7890) - [蒟蒻lndjy的基础组合数学题单](https://www.luogu.com.cn/training/106266) ### 前置芝士 - [P1226 【模板】快速幂||取余运算](https://www.luogu.com.cn/problem/P1226) - [P3383 【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383) - [P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549) --- ### [逆元](https://www.luogu.com.cn/blog/205125/ni-yuan) - [P3811 【模板】乘法逆元](https://www.luogu.com.cn/problem/P3811) - [P5431 【模板】乘法逆元 2](https://www.luogu.com.cn/problem/P5431) - [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613) **前置芝士:EXGCD** --- ### [EXGCD](https://www.luogu.com.cn/blog/205125/kuo-zhan-ou-ji-li-de) - [P5656 【模板】二元一次不定方程 (exgcd)](https://www.luogu.com.cn/problem/P5656) **前置芝士:裴蜀定理** - [P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082) EXGCD常规应用 --- ### [CRT & EXCRT](https://www.luogu.com.cn/blog/205125/zhong-guo-sheng-yu-ding-li-crt) - [P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪](https://www.luogu.com.cn/problem/P1495) **前置芝士:EXGCD** **Warning** - [P4777 【模板】扩展中国剩余定理（EXCRT）](https://www.luogu.com.cn/problem/P4777) **前置芝士:EXGCD** **Warning** - [P3868 [TJOI2009] 猜数字](https://www.luogu.com.cn/problem/P3868) CRT 双倍经验 ~~但你要交换读入顺序，使用龟速乘，处理负数，巴拉巴拉心态碎了一地~~ - [P4774 [NOI2018] 屠龙勇士](https://www.luogu.com.cn/problem/P4774) **前置芝士:Lucas 定理** **Warning** - [P2480 [SDOI2010]古代猪文](https://www.luogu.com.cn/problem/P2480) **Warning** - [P4621 [COCI2012-2013#6] BAKTERIJE](https://www.luogu.com.cn/problem/P4621) **Warning** --- ### Lucas 定理 - [P3807 【模板】卢卡斯定理/Lucas 定理](https://www.luogu.com.cn/problem/P3807) **前置芝士:逆元** - [P2606 [ZJOI2010]排列计数](https://www.luogu.com.cn/problem/P2606) --- ### exLucas - [P4720 【模板】扩展卢卡斯定理/exLucas](https://www.luogu.com.cn/problem/P4720) **前置芝士:EXGCD CRT** --- ### [BSGS & EXBSGS](https://www.luogu.com.cn/blog/205125/post-bsgs) - [P3846 [TJOI2007] 可爱的质数/【模板】BSGS](https://www.luogu.com.cn/problem/P3846) **前置芝士:Hash 欧拉定理 欧拉函数** **Warning** - [P4195 【模板】扩展 BSGS/exBSGS](https://www.luogu.com.cn/problem/P4195) **前置芝士:BSGS 逆元** - [P2485 [SDOI2011]计算器](https://www.luogu.com.cn/problem/P2485) 大杂烩 **Warning** - [P4861 按钮](https://www.luogu.com.cn/problem/P4861) 注意 $\gcd(K,M) \neq 1$ 时才无解，因为此时永远是他们$\gcd$的倍数 - [P4028 New Product](https://www.luogu.com.cn/problem/P4028) ~~好像能暴力水过~~ - [P3306 [SDOI2013] 随机数生成器](https://www.luogu.com.cn/problem/P3306) **Warning** - [SP3105 MOD - Power Modulo Inverted](https://www.luogu.com.cn/problem/SP3105) 同P4195，紫色双倍经验 **Warning** - [P4884 多少个 1？](https://www.luogu.com.cn/problem/P4884) BSGS巧妙应用 ~~还是只有我觉得巧妙？~~+龟速乘 - [P4454 [CQOI2018]破解D-H协议](https://www.luogu.com.cn/problem/P4454) EXBSGS --- ### Miller Rabin & Pollard Rho - [P4718 【模板】Pollard-Rho算法](https://www.luogu.com.cn/problem/P4718) **前置芝士:逆元** --- ### 原根 - [P6091 【模板】原根](https://www.luogu.com.cn/problem/P6091) **前置芝士:欧拉定理** ### 下面两道是[devinwang](https://www.luogu.com.cn/user/156004)倾情推荐的题目 - [P5605 小A与两位神仙](https://www.luogu.com.cn/problem/P5605) **Warning** - [P6730 [WC2020] 猜数游戏](https://www.luogu.com.cn/problem/P6730) **Warning** #### [类欧几里得算法基础](https://www.luogu.com.cn/training/25250) - [类欧blog](https://www.luogu.com.cn/blog/LinearExpectation/Akin-Euclidean-algorithm-Basis) --- ## 公式总结 ### 费马小定理 当 $a,p\in \mathbb{Z}$且 $p$ 为质数，且 $a\not\equiv 0\pmod{p}$ 时有： $a^{p-1}\equiv 1\pmod{p}$ 所以 $a^b\equiv a^{b\bmod (p-1)}\pmod p $ ### 线性求逆元 $\begin{cases} inv[1]=1 \\inv[i]=((p-\left\lfloor \dfrac{p}{i} \right\rfloor)* inv[p\% i])\%p (2\leqslant i< p) \end{cases}$ ### 欧拉函数 $\varphi (n)=n\prod\limits_{i=1}^{s} (1- \frac{1}{p_1})$ 其中 $n={p_1}^{a_1}{p_2}^{a_2}\dots{p_s}^{a_s}$ 是 $n$ 的标准分解 时间复杂度 $\mathcal{O(\sqrt{n})}$ ### 欧拉筛 在 $\mathcal{O(n)}$ 的时间内计算 $\varphi$ 在 $1$ 到 $n$ 处的取值 对于任意$p|n$ $\varphi(n)=\begin{cases} \varphi(\frac{n}{p})*p& p^2|n \\\varphi(\frac{n}{p})*(p-1)&p^2\nmid n \end{cases}$ ### 欧拉定理 当 $a,m\in \mathbb{Z}$，且 $\gcd(a,m)=1$ 时有： $a^{\varphi(m)}\equiv 1\pmod{m}$ 这里 $\varphi(x)$ 是数论中的欧拉函数。 所以 $a^b\equiv a^{b\bmod \varphi(m)}\pmod m$ ### 扩展欧拉定理： 当 $a,m\in \mathbb{Z}$ 时有： $a^b\equiv\left\{\begin{matrix}a^b&,b<\varphi(m)\\a^{b\bmod\varphi(m)+\varphi(m)}&,b\ge\varphi(m)\end{matrix}\right.\pmod m$ ### Lucas 定理 #### 当$p$为质数时成立 $\operatorname{C}(n,m)\%p = \operatorname{C}(n/p,m/p)* \operatorname{C}(n\%p,m\%p)\%p $ $\operatorname{Lucas}(n,m)\%p = \operatorname{Lucas}(n/p,m/p)* \operatorname{C}(n\%p,m\%p)\%p $ 由费马小定理可知：$m!*(n-m)!$ 关于P的逆元就是 $m!*(n-m)!$ 的 $p-2$ 次方 $p$较小的时候预处理出 $1\sim p$ 内所有阶乘 $\%p$的值，然后用快速幂求出逆元，就可以求出解。$p$ 较大的时候只能逐项求出分母和分子模上 $p$ 的值，然后通过快速幂求逆元求解。 ### exLucas 毒瘤，完全不会。 ### 威尔逊定理 $(p-1)! \equiv -1 \pmod p$是 $p$ 为素数的充分必要条件。 详细解释见[这里](https://zhuanlan.zhihu.com/p/452976375)。