Nhận xét

Vì phương trình bậc hai ~ax^2 + bx + c = 0~ có nghiệm ~x = -1~ nên thay ~x = -1~ vào phương trình.

Ta có: ~a.(-1)^2 - b.(-1) + c = 0~ ~\Leftrightarrow a - b + c = 0 \Leftrightarrow a + c = b~.

Bài toán đưa về đếm số bộ ba phần tử của dãy số thoải điều kiện tổng hai phần tử bằng phần tử còn lại.

Subtask ~1~: ~n \le 300~

• Dùng ~3~ lệnh lặp duyệt ~3~ chỉ số ~i, j, k~ sao cho ~u[i] + u[j] = u[k]~ (với ~i \neq j~).
• Độ phức tạp: ~O(n^3)~.

Subtask ~2~: ~n \le 3000~

• Vì các phần tử của dãy số là số dương nên ta có ~a, c < b~.
• Sắp xếp dãy theo thứ tự tăng dần, duyệt xét từng phần tử ~b = u[k]~.
• Với mỗi giá trị ~k~, duyệt các chỉ số ~i~ và tím kiếm nhị phân tìm chỉ số ~j~. Độ phức tạp ~O(n^2logn).
• Hoặc dùng phương pháp ~2~ con trỏ tìm hai chỉ số ~i, j~. Độ phức tạp: ~O(n^2)~.

Subtask ~3~: ~n \le 10^5, u_i \le n~

• Vì các phần tử của dãy là đôi một khác nhau và ~u_i \le n~ nên dãy đã cho chính là hoán vị của ~n~ số nguyên dương đầu tiên.
• Với mỗi giá trị ~k~ ~(1 \le k \le n)~, sử dụng công thức để tính số cách chọn cặp số ~i, j~ sao cho ~i + j = k~.
• Độ phức tạp: ~O(n)~.