P3811 [Template] Modular Multiplicative Inverse

This is a template problem.

Given positive integers $n, p$, find the multiplicative inverses modulo $p$ for all integers in $[1, n]$. The multiplicative inverse of $a$ modulo $p$ is defined as the solution $x$ to $ax\equiv1\pmod p$.

One line with two positive integers $n, p$.

Output $n$ lines, where the $i$-th line denotes the multiplicative inverse of $i$ modulo $p$.

All testdata satisfy $ 1 \leq n \leq 3 \times 10 ^ 6$, $n < p < 20000528 $. The input guarantees that $ p $ is prime. Translated by ChatGPT 5