乘法逆元

逆元作用

用于对于除法的取模运算，下面给出关于除一个数变成乘上他的逆元，在模意义下结果不变的证明：

证明：\(\frac{a}{b}\% p=a*b^{-1}\% p\)

\[\notag \begin{align} \notag b*b^{-1}&\equiv 1 \pmod{p}\\\notag b*b^{-1}\% p&=1\\\notag \frac{a}{b}\% p&=\frac{a}{b}*1\% p\\\notag &=\frac{a}{b}*b*b^{-1}\% p\\\notag &=a*b^{-1}\% p \end{align} \]

证毕

一.单个数逆元求解方法

1. 扩展欧几里得

2. 欧拉函数求解：

   若 $ a\perp p $，则有 $a*a^{\phi(p) -1}\equiv 1 \pmod{p} $

3. 费马小定理：

   若 $ a\perp p $ ，且\(p\)为质数，则有 $a*a^{p-2}\equiv 1 \pmod{p} $

二.线性求逆

1. 用处：用于求出1~n，\(1<=n<=p\) 每一个数在模 \(p\) 的意义下的逆元，时间复杂度为 \(O(n)\)

2. 算法：

   设模数 $p=k*i+r,r\(p\) 的意义下，可以得到\(k*i+r\equiv 0\pmod{p}\)

   \(\because i^{-1}*r^{-1}\equiv i^{-1}*r^{-1}\pmod{p}\)相乘可以得到：

   \[\begin{align} \notag (k*i+r)*i^{-1}*r^{-1}&\equiv 0 \pmod{p}\\\notag \Rightarrow k*i*i^{-1}*r^{-1}+i^{-1}*r*r^{-1}&\equiv 0 \pmod{p}\\\notag \Rightarrow k*r^{-1}+i^{-1}&\equiv 0\pmod{p}\\\notag \Rightarrow i^{-1}&\equiv -k*r^{-1}\pmod{p}\\\notag \because k=\left\lfloor\dfrac{p}{i}\right\rfloor &,r=p\%i\\\notag \Rightarrow i^{-1}\equiv -\left\lfloor\dfrac{p}{i}\right\rfloor*(p\% i)^{-1}&\pmod p\\ \Rightarrow i^{-1}\equiv (p-\left\lfloor\dfrac{p}{i}\right\rfloor)*(p\% i)^{-1}&\pmod p&\\\notag \therefore i^{-1}=(p-p/i)*(p\% i)^{-1}\% p \\\notag 又\because &r

注：\((1)\)这一步是为了保证正数，在模\(p\)的意义下加一个\(p\)没有任何变化

三.离线逆元

问题

对于给定的整数\(a_1,a_2,a_3,..,a_n\)，求其在模 \(p\) 意义下的逆元，其中\(p\) 为质数

1. 首先证明逆元是完全积性的，及：\(a^{-1}*b^{-1}\equiv (a*b)^{-1}\pmod{p}\)

   证明：

   \[\begin{align}\notag a*a^{-1}&\equiv 1\pmod{p}\\\notag b*b^{-1}&\equiv 1\pmod{p}\\\notag \therefore a*b*a^{-1}*b^{-1}&\equiv 1\pmod{p} \\\notag 又\because (a*b)*(a*b)^{-1}&\equiv 1\pmod{p}\\\notag \therefore a^{-1}*b^{-1}&\equiv (a*b)^{-1}\pmod{p} \end{align} \]

2. 设$ per=\prod\limits_{i=1}^{n}a_i $，易得 \(per^{-1}=\prod\limits_{i=1}^{n}a_i^{-1}\)

   \(\therefore a_i^{-1}=per_{i-1}*per^{-1}_{i},per_{i}^{-1}=a_{i+1}*per_{i+1}^{-1}\)

   由此就可以依次推出每一个数的乘法逆元，代码比较好写，所以就不放了

3. 奇技淫巧

   令 \(to_i=\prod\limits_{j=1}^{i}a_j,back_i=\prod\limits_{j=i}^{n}a_j,per^{-1}=\prod\limits_{i=1}^{n}a_i^{-1}\)

   \(\therefore a_i^{-1}=per^{-1}*to_{i-1}*back_{i+1}\)

   这个也可以用来求逆元