Cặp may mắn

Points: 100.00 (partial)

Time limit: 2.0s

Memory limit: 512M

Input: stdin

Output: stdout

Authors:

Lamle, UltimateWiener

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

Copy

6 5
3 1 4 3 2 1

Sample Output

Copy

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

Please read the guidelines before commenting.

2

UltimateWiener commented 1:32:12 pm, 03/02/2025

Test đã được cập nhật lại