시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB150695947.581%

문제

경기북과학고의 알고리즘 동아리인 알프스(ALPS)는 항상 핍박과 멸시에 시달렸다.

“C언어? 그거 완전 문과 녀석들이나 배우는 거 아니야? C ‘언어’ 잖아 언어!”

“과학고에서 과학이 아니라 컴퓨터 같은거나 해대는군… 부끄럽지도 않은거냐고!”

하지만, 알프스 부원들은 알고 있었다. 언젠간 컴퓨터 과학의 위력을 모두에게 보여줄 날이 올 것이라는 것을…


그러던 어느 겨울, 첫 눈이 내리던 날에 의문의 편지 한통이 경기북과학고에 도착했다.

서로 다른 N개의 정수로 이루어진 수열 ${A_1, A_2, …, A_N}$이 있습니다. 또한 소수 $P$와 정수 $K$가 주어집니다. 이 때 $1 ≤ i < j≤ N$ 인 정수쌍 $(i, j)$에 대해서 $A_i^2 + A_i \times A_j + A_j^2$을 $P$로 나눈 나머지가 $K$인 쌍을 ‘좋은 쌍’ 이라고 부릅시다. 편지와 함께 보낸 종이들에 적힌 케이스들에 대해 좋은 쌍의 개수를 각각 구해주세요.

모든 케이스들에 대해서 올바른 값을 구하면 456억원의 상금을 드리도록 하겠습니다.

From,

14기 이채준

편지 옆에는 문제에 해당하는 여러 개의 테스트 케이스들이 빼곡히 적힌 종이들이 함께 있었다.

이 편지를 본 경기북과학고 학생들은 모두가 너 나 할 것 없이 문제를 풀어내는데 집중했다. 하지만 종이에 적힌 값들 중에는 매우 큰 값들도 있었고, 그 까닭에 아무리 수학을 잘하는 학생들이라도 문제를 푸는 데에는 너무 많은 시간이 걸렸다.

모두가 지쳐가는 중 알프스 부원들은 가슴의 울림을 느꼈다. 바로 이 순간이 컴퓨터와 좋은 알고리즘의 위력을 모두에게 보여줄 수 있는 순간이라는 것을 알았던 것이다.

당신은 지금 이 순간만은 명예 알프스 부원이라는 마음으로 이 문제를 해결하기로 결심하였다. 경기북과학고 학생들에게 컴퓨터 과학의 위력과 알프스의 힘을 증명하기 위해 이 문제를 정확하고 빠르게 풀어내는 프로그램을 작성하자!

입력

첫 번째 줄에 $N, P, K$가 주어진다.

두 번째 줄에는 수열 $A_1, A_2, … , A_N$이 주어진다.

출력

입력으로 주어진 케이스에 대해 좋은 쌍의 개수를 출력한다.

제한

  • $2 ≤ N ≤ 10^5$
  • $2 ≤ P ≤ 10^9$
  • $0 ≤ K < P$
  • 모든 $1 ≤ i ≤ N$에 대해 $0 ≤ A_i < P$
  • 모든 $1 ≤ i < j ≤ N$에 대해 $A_i ≠ A_j$를 만족한다.

서브태스크

번호배점제한
110

$N ≤ 3000$

290

추가적인 제한이 없다.

예제 입력 1

4 7 2
0 3 4 6

예제 출력 1

3

출처

High School > 경기북과학고등학교 > GBS Coding Contest 2021 I번

채점 및 기타 정보

  • 예제는 채점하지 않는다.