Ước số (TS10 QNi 2023)

Điểm: 1600 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: divi.inp

Output: divi.out

Tác giả:

Sunlight

Dạng bài

Để chuẩn bị cho cuộc thi quan trọng nhất năm, An đã học cách tìm số ước của một số và nhanh chóng hiểu được các thuật toán khác nhau. Sau đó, trong quá trình tự luyện tập, An quyết định tìm hiểu mối quan hệ giữa một số và số ước của nó.

Cho 2 số nguyên dương $n$ và $k$ , hãy tính số cặp số nguyên $(x,y)$ với $1\le x\le y\le n$ và thỏa mãn đẳng thức:

$k\times d(x)\times d(y)=x\times y$

Trong đó $d(x),d(y)$ lần lượt là số ước nguyên dương của $x$ và $y$

Bạn hãy giúp An tính số cặp $(x,y)$ như vậy

Input, Output và Subtasks

Input: (divi.inp)

Gồm một dòng chứa 2 số nguyên dương $n$ và $k$ ( $1\le n\le 3\times 10^5,1\le k\le 10^9$ )

Output: (divi.out)

Một số nguyên là số cặp số nguyên $(x,y)$ cần tìm

Subtasks

Subtask 1 $(20\%)$ : $1\le n\le 100$ .
Subtask 2 $(20\%)$ : $1\le n\le 600$
Subtask 3 $(20\%)$ : $1\le n\le 4000$
Subtask 4 $(20\%)$ : $1\le n\le 10^4$
Subtask 5 $(20\%)$ : Không có giới hạn gì thêm.

Sample

Input (divi.inp)

8 3

Output (divi.out)

Note

Có 2 cặp $(x,y)$ thỏa mãn là $(3,8)$ và $(6,8)$ . Chúng ta hãy kiểm tra 2 cặp này:

Với cặp $(x,y)=(3,8)$ . Số $x=3$ có 2 ước nguyên dương là $1$ và $3$ , do đó $d(x)=2$ . Số $y=8$ có $4$ ước nguyên dương là $1,2,4,8$ , do đó $d(y)=4$ . Vì $k\times d(x)\times d(y)=3\times 2\times 4=24$ và $x\times y=3\times 8=24$ nên $k\times d(x)\times d(y)=x\times y$
Với cặp $(x,y)=(6,8)$ . Số $x=6$ có 4 ước nguyên dương là $1,2,3,6$ , do đó $d(x)=4$ . Số $y=8$ có $4$ ước nguyên dương là $1,2,4,8$ , do đó $d(y)=4$ . Vì $k\times d(x)\times d(y)=3\times 4\times 4=48$ và $x\times y=6\times 8=48$ nên $k\times d(x)\times d(y)=x\times y$

Sample

Input (divi.inp)

25 9

Output (divi.out)

Note

Các cặp số thỏa mãn: $(9,9), (9,18),(9,24),(18,18),(18,24),(24,24)$

Bình luận

Không có bình luận nào.