 Batch modular inversion

For invertible residue classes $a_1,\dots ,a_n$, all their modular inverses can be recovered with one inversion and a linear number of multiplications. Store prefix products $P_i=a_1\cdots a_i$, invert $P_n$ once, and sweep backward: if the current inverse is $P_i^{-1}$, then $a_i^{-1}=P_i^{-1}{P}_{i-1}$ and $P_{i-1}^{-1}=P_i^{-1}{a}_i$. The same construction works in any commutative group.