数论同余学习笔记 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\),则

\[ax\equiv -b\pmod p \]

为得到 \(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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程