Đếm cặp
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Đếm số cặp chỉ số \((i,j)\) thỏa mãn:
- \(1 \le i \le j \le n\);
- \(a_i + a_j^2=K\) với \(K\) cho trước.
Input
- Dòng đầu tiên gồm 2 số nguyên dương \(N\) và \(K\) \((N \le 10^5,K \le 10^9)\)
- Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)
Output
- In ra số cặp \((i,j)\) thỏa mãn.
Example
Test 1
Input
3 5
1 2 2 Output
2
Bình luận
bài này O(nlogn) mới full được nên không dùng được 2 vòng for lồng nhau
để full thì sử dụng sort kết hợp với tìm kiếm nhị phân
7 bình luận nữa