乘法逆元

若 $ax\equiv 1\pmod{p}$，则称 $x$ 是模 $p$ 意义下 $a$ 的乘法逆元，记作 $a^{-1}$。

显然，它相当于模意义下 $a$ 的倒数。不那么严谨地说，模意义下除以 $a$ 就是乘 $a^{-1}$。

由于求逆元相当于求 $ax+py=1$ 的一组整数解，所以可以使用扩展欧几里得法。

void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}

复杂度为 $O(\log a)$。

由费马小定理（$p$ 为质数）： $$ a^{p}\equiv a\pmod{p} $$ 因此 $(a,p)=1$ 时， $$ a^{-1}\equiv a^{p-2}\pmod{p} $$ 复杂度为 $\Theta(\log p)$。

首先，$1^{-1}\equiv 1\pmod p$；

其次，考虑 $i^{-1}$，令 $k=\left\lfloor\dfrac{p}{i}\right\rfloor,j=p\bmod i$，有 $p=ki+j$，则模意义下有 $ki+j\equiv 0\pmod p$；两边同时乘 $i^{-1}j^{-1}$： $$ \begin{aligned} kj^{-1}+i^{-1}&\equiv 0&\pmod p\\ i^{-1}&\equiv -kj^{-1}&\pmod p\\ i^{-1}&\equiv -\left\lfloor\dfrac{p}{i}\right\rfloor(p\bmod i)^{-1}&\pmod p\\ \end{aligned} $$ 递推即可，时间复杂度 $\Theta(n)$。

注意到 $0^{-1}$ 未定义，因此对任意 $i\mid p$，$i^{-1}$ 同样未定义。

注意到这种方法同样可以单点求逆元，现在已经证明其复杂度为 $O(\sqrt[3]{n\ln n})$，且 $\Omega(\dfrac{\ln n}{\ln\ln n})$，同时观察到可能是 $O(\log n)$ 的。

给定序列 $a$，线性求序列中每个数的逆元。

• 首先，求出 $a$ 的前缀积 $s$；

• 然后，使用快速幂或扩展欧几里得法求 $s_n$ 的逆元 $v_n$；

• 由 $v_{i}=v_{i+1}\cdot a_{i+1}$，可以递推出整个序列 $v$；

• $a_{i}=s_{i}\cdot v_{i-1}$。

时间复杂度 $\Theta(n+\log p)$。

存在一种 $\Theta(p^{2/3})$ 预处理，在线 $\Theta(1)$ 查询的算法。

第 $i$ 个 Farey 序列记作 $F_i$，是把分母小于等于 $i$ 的所有最简真分数从小到大排成的序列；特别地，序列的首项是 $\dfrac{0}{1}$，末项为 $\dfrac{1}{1}$。

$$ \begin{array}{lllllllllllll} F_1=\bigg\{&\dfrac{0}{1},&&&&&&&&&&\dfrac{1}{1}&\bigg\}\\ F_2=\bigg\{&\dfrac{0}{1},&&&&&\dfrac{1}{2},&&&&&\dfrac{1}{1}&\bigg\}\\ F_3=\bigg\{&\dfrac{0}{1},&&&\dfrac{1}{3},&&\dfrac{1}{2},&&\dfrac{2}{3},&&&\dfrac{1}{1}&\bigg\}\\ F_4=\bigg\{&\dfrac{0}{1},&&\dfrac{1}{4},&\dfrac{1}{3},&&\dfrac{1}{2},&&\dfrac{2}{3},&\dfrac{3}{4},&&\dfrac{1}{1}&\bigg\}\\ F_5=\bigg\{&\dfrac{0}{1},&\dfrac{1}{5},&\dfrac{1}{4},&\dfrac{1}{3},&\dfrac{2}{5},&\dfrac{1}{2},&\dfrac{3}{5},&\dfrac{2}{3},&\dfrac{3}{4},&\dfrac{4}{5},&\dfrac{1}{1}&\bigg\} \end{array} $$

注意到 Farey 序列可以迭代生成，每次只需选择 $F_{n-1}$ 中每对相邻的 $\dfrac{a}{b},\dfrac{c}{d}$，满足 $b+d=n$，将 $\dfrac{a+c}{b+d}$ 放在中间即可。

同时，Farey 序列有性质：$bc-ad=1$。

我看到很多博客提到一个定理：

对于任意整数 $n\le 2$ 和任意实数 $v\in [0,1]$，总能在 $F_{n−1}$ 找到 $\dfrac{x}{y}$ 满足 $\left|v−\dfrac{x}{y}\right|≤\dfrac{1}{yn}$ 。更强地，这个 $\dfrac{x}{y}$ 一定是 $v$ 序列中最接近 $v$ 的第一个分数。

实际上，如果引入渐进分数，有另一个不等式：

对实数 $x$ 与渐进分数 $\dfrac{p_k}{q_k}$ ，有 $$ \dfrac{1}{q_k(q_k+q_{k+1})}<\left|x-\frac{p_k}{q_k}\right|<\dfrac{1}{q_kq_{k+1}} $$

这个不等式更紧一些，因为 $q_{k+1}$ 不会比 $n$ 更小。

我们固定 $n$，对于 $a$ 令 $v=\dfrac{a}{p}$ 并找到 $\dfrac{x}{y}$ 满足 $\left|\dfrac{a}{p}-\dfrac{x}{y}\right|\le\dfrac{1}{yn}$。即 $|ay-px|\le\left\lfloor\dfrac{p}{n}\right\rfloor$。也就是说 $ay\equiv u\pmod p$，其中 $|u|\le \left\lfloor\dfrac{p}{n}\right\rfloor$。注意到 $a^{-1}=u^{-1}y\pmod p$，我们只需预处理 $O\left(\left\lfloor\dfrac{p}{n}\right\rfloor\right)$ 个数的逆元。

注意到序列中 $\left\lfloor\dfrac{xn^2}{y}\right\rfloor$ 互不相同，我们开一个长 $n^2$ 的 $0/1$ 数组记录是否有 $\left\lfloor\dfrac{xn^2}{y}\right\rfloor$ 等于 $i$。将序列求前缀和即可 $O(1)$ 查大于或小于 $\dfrac{x}{y}$ 的的第一个数。