Sau khi học phương pháp giải phương trình bậc hai, các bạn học sinh được thầy giáo cho các bài tập để luyện tập. Các học sinh rất hào hứng đia nhau giải các bài tập xem ai hoàn thành sớm nhất. Để tăng thêm phần hấp dẫn, thầy giáo đã yêu cầu các học sinh làm bài toán ngược lại: cho trước ~n~ số nguyên dương đôi một khác nhau ~u_1, u_2, \dots, u_n~, hãy tìm ba số khác nhau trong dãy số đã cho làm ba hệ số ~a, b, c~ để phương trình bậc hai ~ax^2 + bx + c = 0~ có nghiệm là ~-1~. Khi bắt tay vào làm bài, các học sinh phái hiện ra rằng có rất nhiều cách chọn ra các bộ ba hệ số ~a, b, c~ thoả điều kiện và các em muốn đếm xem có tất cả bao nhiên cách chọn như thế.
Yêu cầu: Hãy cho biết có bao nhiêu cách chọn ba phần tử khác nhau trong dãy số đã cho làm ba hệ số ~a, b, c~ để phương trình bậc hai ~ax^2 + bx + c = 0~ có nghiệm là ~-1~.
Dữ liệu vào
Cho từ tệp văn bản PTB2.INP
có dạng:
- Dòng thứ nhất ghi số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
- Dòng thứ hai ghi ~n~ số nguyên dương ~u_1, u_2, \dots, u_n~ ~(0 < u_i \le 10^9,~ ~i = 1..n; u_i \neq u_j~ ~\forall i \neq j)~. Các số trên cùng một dòng cách nhau một dấu cách.
Kết quả
Ghi ra tệp văn bản PTB2.OUT
gồm một dòng ghi một số nguyên là số cách tìm được.
Ràng buộc
- Có ~70\%~ số test ứng với ~70\%~ số điểm có giá trị ~n \le 300~.
- Có ~20\%~ số test ứng với ~20\%~ số điểm có giá trị ~n \le 3000~.
- Có ~10\%~ số test ứng với ~10\%~ số điểm có giá trị ~n \le 10^5, u_i \le n~.
Ví dụ
Dữ liệu vào
6
4 2 13 7 5 10
Dữ kết quả
2
Giải thích
Có ~2~ cách chọn:
- Cách ~1~: ~a = 2, b = 7, c = 5~; phương trình ~2x^2 + 7x + 5 = 0~ có nghiệm ~x = -1~.
- Cách ~2~: ~a = 5, b = 7, c = 2~; phương trình ~5x^2 + 7x + 2 = 0~ có nghiệm ~x = -1~.
Bình luận