26521번 - 연립방정식

$n$개의 서로 다른 양의 정수 $a_1, a_2, \cdots ,a_n$ 이 주어진다.

다음을 만족하는 $n$개의 정수 $x_1, x_2, \cdots ,x_n$ 이 존재한다면 이들을 $10^9+7$로 나눈 나머지를 한 줄에 공백으로 구분하여 출력하고, 존재하지 않는다면 NO를 출력하시오.

• $0 \leq m \leq n-1$ 인 모든 정수 $m$에 대하여,

$$ \sum_{i=1}^{n} \frac {{a_i}^{m}}{x_i} = \begin{cases} 0 & \text{($0 \leq m < n-1$)}\\ 1 & \text{($m=n-1$)}\\ \end{cases} $$

첫 번째 줄에 양의 정수의 개수 $n$이 주어진다. $(2 \leq n \leq 5\,000)$

두 번째 줄에 $a_1$, $a_2$, $\cdots$, $a_n$이 공백으로 구분되어 주어진다. $(1 \leq a_i \leq 10^9)$

조건을 만족하는 $n$개의 정수 $x_1$, $x_2$, $\cdots,$ $x_n$ 이 존재한다면 이들을 $10^9+7$로 나눈 나머지를 한 줄에 공백으로 구분하여 출력하고, 존재하지 않는다면 NO를 출력한다.

이 조건을 만족하는 $x_1, x_2, ... ,x_n$ 이 존재한다면 유일함을 보일 수 있다. 임의의 정수 $a$와 양의 정수 $b$에 대해서, $a=bq+r(0 \leq r < b)$이 되는 정수 $q$와 $r$이 유일하다. 이때 $r$을 $a$를 $b$로 나눈 나머지로 정의한다.