noip复习——逆元
逆元,即对给定\(a,p\ (a \perp p)\),求\(x\)使得\(ax \equiv 1 \ (\bmod p)\)
逆元可以看做\(a\)在模\(p\)意义下的\(a^{-1}\)。因此,在模\(p\)意义下,可以用乘\(a\)的逆元的方式来代替除以\(a\)操作
求单个数的逆元
费马小定理求逆元
当\(p\)是质数且\(a\perp p\)时 $$a^{p-1}\equiv1\quad (\bmod p) $$
方程两边同时乘\(a^{-1}\),可以发现$$a^{-1}\equiv a ^{p-2}\quad(\bmod p)$$
可以直接快速幂求 传送门
欧拉定理求逆元
欧拉定理可以适用于满足\(a\perp p\)的情况 $$a^{\varphi(p)}\equiv 1\quad (\bmod p) $$
同理可得$$a^{-1}\equiv a^{\varphi(p)-1} \quad (\bmod p) $$
现在的问题变成了,如何求欧拉函数?
1.线性筛\(O(p)\)求
适用于多个模数的情况 传送门
如果是单一模数怎么办呢?有更高效的做法
2.\(O(\sqrt{p})\)做法
\]
其中,\(i\)是\(p\)的所有质因子
#define LL long long
LL get_phi(LL n)
{
LL sum = n;
for (LL i = 1; i * i <= n; ++i)
if (n % i == 0)
{
sum -= sum / i;
while (n % i == 0)
n /= i;
}
if (n > 1)
sum -= sum / n;
return sum;
}
exgcd求逆元
exgcd可以求解方程组\(ax+by=c\)的解,而求\(a\)在模\(p\)下的逆元可以转化为求\(ax+py=1\)的解
求多个数的逆元
线性求1~n的逆元
令\(p=ki+r,k=\lfloor\frac pi \rfloor. r=p \bmod i\)
则有\(ki+r \equiv 0\quad (\bmod p)\),乘\(i^{-1},r^{-1}\)可得\(kr^{-1}+i^{-1}\equiv 0\quad (\bmod p)\)
所以\(i^{-1}=-r^{-1}\lfloor\frac pi \rfloor\)
显然可以递推求解
线性求n个数的逆元
先预处理出这n个数的前缀积\(sum_i\),然后求出这n个数积的逆元\(suminv_n\),那么\(suminv_{i-1}=suminv_i*a_i\),\(inv_i=suminv_{i}*sum_{i-1}\)。
最新文章
- zookeeper原理解析-选举
- Windows桌面共享中一些常见的抓屏技术
- 跨平台日志清理工具 Log-Cutter v2.0.1 RC-1 发布
- 1018Mysql分表分库
- .net图片验证码生成、点击刷新及验证输入是否正确
- usb驱动开发7之接口描述符
- C#装箱和拆箱(值类型和引用类型之间的转换)
- POJ 3286 How many 0&#39;s?(几多0?)
- linux套件安装过程中configure,make,make install的作用
- VMware虚拟机打开不了操作系统的解决方案
- 利用Format函数格式化时间和日期
- codefirst mvc Self referencing loop detected for property
- 个人linux简单笔记,随时更新
- JAVA进阶--ThreadPoolExecutor机制
- 201621123031 《Java程序设计》第11周学习总结
- Dynamics CRM2013 从外部系统取到CRM系统的用户头像
- CentOS下MySQL的安装
- Simple Recurrent Unit,单循环单元
- react-router 4.0(四)跳转404
- python 使用ElementTree解析xml