Tổng tích

Xem PDF
Tác giả:
cuom1999
Dạng bài
Điểm: 450 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong quá trình nghiên cứu kiểm thử bằng đột biến (mutation testing), Lương nhận ra có những cặp số đặc biệt mà khi thay phép cộng thành phép nhân, đáp số vẫn không đổi. Lưu ý thêm rằng, phép tính trong máy tính đều được mod cho một số nào đó (thường là \(2^{32}\)). Vì thế Lương hỏi bạn bài toán sau:

Cho một dãy số tự nhiên \(a_1,a_2,\cdots,a_n\) và một số nguyên dương \(p\). Hãy tính số cặp \(i<j\) sao cho \(a_i+a_j\) và \(a_i∗a_j\) có cùng số dư khi chia cho \(p\).

Input

  • Dòng đầu tiên chứa hai số nguyên dương \(n,p (1 \leq n \leq 5∗10^5,2 \leq p \leq 10^9)\).
  • Dòng thứ hai chứa \(n\) số tự nhiên \(a_1,a_2,\cdots,a_n (0 \leq a_i \leq 10^9)\).

Output

  • In ra một dòng là đáp số cần tìm.

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): \(p=10^9\) và \(0 \leq a_i \leq 10^4\)
  • Subtask \(2\) (\(25\%\) số điểm): \(p \leq 2000\)
  • Subtask \(3\) (\(25\%\) số điểm): p là số nguyên tố.
  • Subtask \(4\) (\(25\%\) số điểm): không có điều kiện gì thêm.

Example

Test 1

Input 
4 2
0 1 2 3
Output 
1

Test 2

Input 
3 3
2 5 3
Output 
1
Note
  • Trong test ví dụ 1, chỉ có một cặp \((a_1,a_3)=(0,2)\) là thỏa mãn vì \((0+2)\) \(mod\) \(2=0\) và \((0∗2)\) \(mod\) \(2=0\).
  • Trong test ví dụ 2, chỉ một cặp \((a_1,a_2)=(2,5)\) thỏa mãn vì \((2+5)\) \(mod\) \(3=1\) và \((2∗5)\) \(mod\) \(3=1\).

Bình luận