14850번 - doju

doju의 취미는 BOJ 문제에 새로운 데이터를 추가하는 것이다. doju는 자신이 추가한 데이터로 인해 틀린 사람을 보면 매우 행복해한다.

오늘 doju가 데이터를 만들 문제의 입력 형식은 다음과 같다.

첫째 줄에 정수 n (1 ≤ n ≤ max_n)이 주어진다. 둘째 줄에는 n개의 서로 다른 정수 a₁, a₂, ..., a_n (1 ≤ a_i ≤ max_a)가 오름 차순으로 주어진다.

이 문제의 올바른 풀이는 먼저, a₁, a₂, ..., a_n의 최대공약수 g를 구하고 x = a_n/g - n을 구한다. 그 다음, x가 홀수면 "odd"를, 짝수면 "even"을 출력해야 한다.

그런데, x를 아래와 같은 두 가지 방법으로 잘못 구해도 이 문제를 간혹가다가 맞을 수 있다.

1. x = a_n/g
2. x = a_n-n

max_n, max_a, q가 주어졌을 때, 잘못 구한 두 방법을 모두 틀리게 만드는 데이터의 개수를 q로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 max_n, max_a, q가 주어진다. (1 ≤ max_n ≤ 30,000, max_n ≤ max_a ≤ 10⁹, 10⁴ ≤ q ≤ 10⁵+129)

첫째 줄에 문제에 주어진 두 방법을 모두 틀리게 만드는 데이터의 개수를 q로 나눈 나머지를 출력한다.

첫 번째 예제의 경우 다음과 같은 4가지가 가능하다.

1
2

1
4

1
6

3
2 4 6