科技：在线 O(B)-O(log(p / B)) 求逆元/ 俗称在线 O(1) 求逆元（？）
离线 \(O(1)\) 求逆元
求出 \((\prod x)^{-1}\) 即可。
线性求逆元
先线性求逆元预处理出 \(x \le B\) 的 \(x^{-1}\)，设为 \(inv_x\)。
对于一个 \(x\)，令 \(p = qx + r\)。
\[0\equiv 0\pmod p \to 0\equiv p\equiv qx + r\to x^{-1}\equiv -q\cdot r^{-1}
\]
在线 \(O(1)\) 求逆元\(^{\text{但好像不是O(1)}}\)
但是若 \(r> \frac{x}{2}\) 怎么办呢
还有一个等式
\[0\equiv p\equiv (q + 1)x + r - x
\]
发现得到了 \(x - r\) 有 \(x^{-1}\equiv (q + 1)\cdot (x - r)^{-1}\)
于是每次要求的都会 \(< \frac x 2\) 做到 \(O(log \frac p B)\)
怎么说呢，因为 \(p\) 是定的，\(B\) 也是定的，所以是 \(O(1)\)/yiw/lh