Cặp may mắn
View as PDF
Submit solution
Points:
100.00 (partial)
Time limit:
2.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Authors:
Problem type
Tèo đang có một dãy ~a~ gồm ~n~ số nguyên dương. Nhân dịp năm mới, Tèo chuẩn bị quay lô tô để farm (đốt) tiền, nhưng anh không biết sẽ chọn số nào để đặt. Thay vào đó, Tèo quyết định sẽ dùng dãy a để chọn giúp anh, Tèo định nghĩa một cặp ~(i, j)~ ~(i < j)~ là may mắn khi ~a[i] \cdot a[j]~ là số chính phương và ~a[i] + a[j] \leq x~. Nhưng trước hết, Tèo nhờ bạn đếm xem trong dãy ~a~ có bao nhiêu cặp may mắn.
Input
Dòng đầu nhập vào hai số ~n~, ~x~ ~(n \leq 10^5, x \leq 2 \cdot 10^6)~.
Dòng thứ hai nhập ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(a_i \leq 10^6)~.
Output
- In ra kết quả của bài toán
Sample Input
6 5
3 1 4 3 2 1
Sample Output
3
Note
Các cặp thỏa mãn là ~(2,3),(2,6),(3,6)~. Vì vậy, đáp án là ~3~.
Constraint
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | ~25 \%~ | ~n \leq 10^3~ |
| ~2~ | ~25 \%~ | ~a_i \leq 10^3, x \leq 2 \cdot 10^3~ |
| ~3~ | ~50 \%~ | Không ràng buộc gì thêm |
Comments
Test đã được cập nhật lại