소수 \(p = 10^9+7\)을 법으로, \(1\)부터 \(n\)까지 각 정수의 모듈러 역원을 출력하시오. \(i\)의 역원은 \(i \cdot x \equiv 1 \pmod p\)를 만족하는 유일한 \(x \in [1, p-1]\)이다. \(\text{inv}[i] = -\lfloor p/i \rfloor \cdot \text{inv}[p \bmod i] \bmod p\)를 이용하면 모든 \(n\)개의 역원을 \(O(n)\)에 구할 수 있다.

정수 \(n\)이 주어진다 (\(1 \le n \le 5 \times 10^4\)).

한 줄에 \(n\)개의 정수를 출력한다: \(1, 2, \dots, n\)의 역원을 순서대로 공백 하나로 구분하여 출력한다.

riseoj 작성

출처 RiseOJ Basics