solution

Tính nghịch đảo modular của $1,2,\dots,k$

Để tính nghịch đảo của mọi số trong $1..k$ modulo số nguyên tố $p$ trong $O(k)$, dùng công thức truy hồi:

$\mathrm{inv}[1]=1,\qquad \mathrm{inv}[i] = -\left\lfloor \frac{p}{i}\right\rfloor\cdot \mathrm{inv}[p\bmod i] \bmod p$

Cho $k$ và số nguyên tố $p>k$. In trên một dòng các giá trị $\mathrm{inv}[1],\dots,\mathrm{inv}[k]$ (mỗi giá trị trong $[0,p)$), cách nhau bởi dấu cách.

Ví dụ

Với $p=7$: $\mathrm{inv}[1..6]=1,4,5,2,3,6$.