32228번 - 등차수열 만들기 서브태스크스페셜 저지

동우는 등차수열을 좋아한다. 재우는 서로소를 좋아한다.

어느 날 재우는 동우에게 $2$이상의 양의 정수 $M$과 $N$개의 정수 $A_1,A_2,\cdots ,A_N$을 주었다. 재우는 서로소를 좋아하기 때문에 모든 $A_i$는 $M$과 서로소이다.

동우는 주어진 정수들을 $K$제곱하여$\bmod M$에서 등차수열로 만들고자 한다.

일반적으로 어떤 수열 $B_1,B_2,\cdots ,B_N$이 등차수열이라는 것은, 모든 $1\le i<N$에 대하여 $B_{i+1}-B_i=d$로 일정한 것을 의미한다. 비슷하게$\bmod M$에서 등차수열이라는 것은, $B_{i+1}-B_i\equiv d\pmod M$으로 일정한 것을 의미한다.

$A_1^K,A_2^K,\cdots ,A_N^K$가$\bmod M$에서 등차수열이 되도록 하는 $1$이상 $M$이하의 정수 $K$가 존재하는지 찾아보자. 단, 수열의 순서를 바꿀 수는 없다.

첫 번째 줄에 정수 $N(3\le N\le 10^6)$과 $M(2\le M\le 10^9)$이 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $A_1,A_2,\cdots ,A_N( 1\le A_i<M$; $\gcd\left( A_i,M \right) =1)$이 공백으로 구분되어 주어진다.

$A_1^K,A_2^K,\cdots ,A_N^K$가$\bmod M$에서 등차수열이 되도록 하는 $1$ 이상 $M$ 이하의 정수 $K$가 존재하면 $K$를 출력하고, 존재하지 않으면 -1을 출력한다.

범위 내에 가능한 $K$가 여러 개라면, 아무거나 하나 출력한다.