逆元

定义

　　在模\(p\)意义下，对于一个数\(a\)，如果存在一个数\(b\)，使得\(a \times b \equiv 1 \pmod p\)，则\(b\)是\(a\)的逆元，记作\(a^{-1}\)。同时，\(a\)和\(a^{-1}\)互为逆元。

　　逆元存在的条件：\((a,p)=1\)。直接用裴蜀定理看看？

　　上面的\(\frac{a}{b}\)可以写成\(a\times b^{-1}\)，若逆元存在，同余性质\(3\)就成了。

性质

　　1、存在唯一性

　　模\(p\)意义下，对于\(a\)而言，如果其存在逆元，则逆元只有一个\(a'=a^{-1}\)。

　　假设存在另一个逆元\(a''\times a \equiv 1\)，由\(a'\ \times a \equiv 1 \pmod p\)得：\((a''-a') \times a \equiv 0 \pmod p\)，有\(a \neq 0\)，所以有\(a''-a'\equiv 0 \pmod p\)，于是\(a' \equiv a'' \pmod p\)。

　　2、完全积性函数

　　也就是\((ab)^{-1} \equiv a^{-1} \times b^{-1} \pmod p\)。

　　考虑有\(a \times a^{-1} \equiv 1 \pmod p\)和\(b \times b^{-1} \equiv 1 \pmod p\)，乘到一起就是\((ab)(a^{-1}\times b^{-1}) \equiv 1 \pmod p\)，所以\((ab)^{-1} \equiv a^{-1}\times b^{-1} \pmod p\)。

　　如何求解逆元呢？

求解1：暴力

　　~~一个一个试呗~~（不多说）

　　复杂度：\(\text{O}(p)\)。

求解2：费马小定理

　　定理：当\(p\)为素数时，\(a^{p-1}\equiv 1 \pmod p\)

　　\(Proof\)：

\[构造一个缩系A=\{x\mid (x,p)=1\}，则\mid A\mid =\varphi(p)=p-1，\varphi(p)表示与p互质的数个数 \]

\[对于a \neq 0构造集合B=\{ax\mid x \in A\}，易证在元素模p意义下：A=B \]

\[\therefore 在模p意义下，\prod_{x \in A}x \equiv \prod_{y \in B}y \equiv \prod_{x \in A}ax \equiv a^{p-1}\prod_{x \in A}x \pmod p \]

\[即证a^{p-1}\equiv 1 \pmod p \]

　　所以要求\(a^{-1}\)，只需求\(a^{p-2}\)即可。

　　复杂度：\(\text{O}(\log p)\)。

求解3：扩展欧几里得

　　\(p\)不是素数时咋办？写个式子你就明白了：\(ax+py=1\)，\(x\)就是\(a^{-1}\)。

　　复杂度：\(\text{O}(\log p)\)。

求解4：欧拉筛

　　由完全积性的性质得到的方法。这个方法可以批量求解，但是对于\(p\)是素数的情况下仍然需要前面的方法，复杂度\(\text{O}(n+素数\times \log n)\)。

求解5：线性递推

　　假如我们要求\(a\)在模\(p\)意义下的逆元，构造式子\(p=qa+r\)，发现\(q=\lfloor \frac{p}{a} \rfloor\)，\(r=p \bmod a\)。

　　然后我们有：

\[r\times r^{-1} \equiv 1 \pmod p \]

　　用\(r=p-qa\)替换得：

\[(p-qa)\times r^{-1} \equiv 1 \pmod p \]

　　然后：

\[-qa\times r^{-1} \equiv 1 \pmod p \]

　　所以我们就有了：

\[a^{-1} \equiv -q \times r^{-1} \pmod p \]

　　用最上面的东西替换就得到了：

\[a^{-1} \equiv -\lfloor \frac{p}{a} \rfloor \times (p \bmod a)^{-1} \pmod p \]

　　于是我们就可以线性求解了。

inv[1] = 1;
rep(i, 2, n) inv[i] = 1ll*(P-P/i)*inv[P%i]%P;

　　复杂度：\(\text{O}(p)\)。

　　但是这里有缺陷：就是逆元必须从前往后推，如果随机性地从中挑些数出来询问，而\(p\)又很大，就会\(\text{TLE}\)。所以根据题目需要进行选择（可能还需要巧妙的方法）。

解法6：另一种方法

　　前提是得到了模数\(p\)和要询问的数组\(A\)，要求\(A_i\)的逆元。

　　令\(S=\prod A_i\)，\(A_i\)的逆元就是\(\frac{S/A_i}{S}\)。我们不希望用费马小定理求多次逆元，这样复杂度很大。我们只要求出\(S^{-1}\)即可，这一步的复杂度为\(\text{O}(\log p)\)。

　　对于\(S/A_i\)，我们维护一个前缀\(P_i=\prod_{x<i}A_x\)，维护一个后缀\(Q_i=\prod_{x>i}A_x\)，则\(S/A_i = P_i\times Q_i\)（正好少乘了一个\(A_i\)），于是问题得解。这一步的复杂度只与查询数多少有关，为\(\text{O}(n)\)。

　　总复杂度：\(\text{O}(n+\log p)\)。正好弥补了解法\(5\)的缺陷。

逆元

逆元

定义