数论同余学习笔记 Part 2
2022/2/8 23:51:17
本文主要是介绍数论同余学习笔记 Part 2,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
逆元
准确地说,这里讲的是模意义下的乘法逆元。
定义:如果有同余方程 \(ax\equiv 1\pmod p\),则 \(x\) 称为 \(a\bmod p\) 的逆元,记作 \(a^{-1}\)。
作用是抵消乘法,即 \(x\cdot a\cdot a^{-1}\equiv x\pmod p\)
进一步可以得到 \(\frac xa\equiv x\times a^{-1}\pmod p\),这也是分数取模的计算方式
最通用的求法是 exgcd 。
\(ax\equiv 1\pmod p\) 等价于 \(ax+py=1(x,y\in\Z)\),可直接用 exgcd 求解。时间复杂度 \(O(\log p)\)。
这也表明当且仅当 \(\gcd(a,p)=1\) 时,\(a\bmod p\) 的逆元存在。
OI 中为了方便,往往选择一个大质数作为模数 \(p\),以保证在给定的数据范围内逆元始终存在。
下文仅讨论 \(p\) 为质数的情况,且默认其它数均小于 \(p\)
这里我们不加证明地引入费马小定理:若 \(p\) 为质数,\(a,p\) 互质,则 \(a^{p-1}\equiv 1\pmod p\)。
则 \(a^{-1}\equiv a^{p-2}\pmod p\),故直接用快速幂计算 \(a^{p-2}\bmod p\) 即得 \(a^{-1}\)。
时间复杂度是 \(O(\log p)\),单次求逆元似乎没有更优的做法了
但要算多个逆元时有一些技巧可以做到线性
洛谷P3811 【模板】乘法逆元
给定 \(n,p\),求 \(1\sim n\) 中所有整数在模 \(p\) 意义下的逆元。
\(1\le n\le 3\times10^6,n<p<20000528\),保证 \(p\) 为质数
有一个经典的线性递推求 \(1\sim n\) 逆元的方法。
比如我们当前求的是 \(x^{-1}\)。
设 \(p=ax+b\),则
为得到 \(x^{-1}\),将两边同除以 \(x\)
\[a\equiv -b\cdot x^{-1}\pmod p \]整理一下
\[x^{-1}\equiv -a\cdot b^{-1}\pmod p \]代入 \(a=p/x,b=p\%x\)
\[x^{-1}\equiv -(p/x)\cdot (p\% x)^{-1}\pmod p \]即得递推式。
核心代码:
inv[1]=1; for (int i=2; i<=n; ++i) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
再讲一个有点奇怪的做法
所求即 \(inv(x)=x^{p-2}\)。注意到这是个积性函数。
于是可以用欧拉筛去筛它,当 \(x\) 为质数时用快速幂直接计算。
由于 \(1\sim n\) 的质数大约有 \(\ln n\) 个,这个做法的时间复杂度是 \(O\left(\dfrac{n\log p}{\ln n}+n\right)\),比 \(O(n)\) 略慢。
实际上这个技巧原本是 \(O\left(\dfrac{n\log k}{\ln n}+n\right)\) 计算 \(1^k\sim n^k\),这里令 \(k=p-2\) 强行套用了而已
也可以考虑预处理阶乘:
fac[0]=1; for (int i=1; i<=n; ++i) fac[i]=1ll*fac[i-1]*i%p; inv[n]=power(fac[n],p-2,p); // 快速幂计算逆元 for (int i=n; i; --i) inv[i-1]=1ll*inv[i]*i%p;
其中 fac,inv
分别是阶乘及其逆元。显然 \(x^{-1}\equiv fac_x\cdot inv_{x-1}\pmod p\)。
时间复杂度 \(O(n)\)。在一些组合计数的题中会更自然地用到。
然后是第二道板子题
洛谷P5431 【模板】乘法逆元 2
给定 \(n\) 个正整数 \(a_i\),求它们在模 \(p\) 意义下的逆元。
为减少输出量,给定常数 \(k\),只需输出 \(\sum\limits_{i=1}^n\dfrac{k^i}{a_i}\)。
\(1\le n\le 5\times10^6,2\le k<p\le 10^9,1\le a_i<p\),保证 \(p\) 为质数
令 \(A\) 为所有数的积,\(pre_i\) 为前缀积,\(suf_i\) 为后缀积,则 \(a_i^{-1}=A^{-1}\cdot pre_{i-1}\cdot suf_{i+1}\)。
于是显然可以 \(O(n)\) 计算。
本质上是因为算除法(逆元)要一个 log ,而乘法是常数级,于是化除为乘减少计算量
感觉其实就是通分(?)
这篇关于数论同余学习笔记 Part 2的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南