Cho hai số nguyên dương \(n\) và \(k\). Đếm số cặp \((x, y)\) với \(1 \le x \le y \le n\) thỏa mãn:
\begincenter
$
k \times d(x) \times d(y) = x \times y
$
\endcenter
trong đó \(d(x)\) là số ước nguyên dương của \(x\).
Input
Vào từ file DIVI.INP một dòng chứa hai số nguyên dương \(n, k\) (\(1 \le n \le 3 \times 10^5\), \(1 \le k \le 10^9\)).
Output
Ghi ra file DIVI.OUT một số nguyên là số cặp \((x, y)\) thỏa mãn.
Example
Test 1
Input
8 3Output
2Note
Trong ví dụ thứ nhất ta có \(n = 8\) và \(k = 3\). Có 2 cặp \((x, y)\) thõa mãn \((3, 8)\) và \((6, 8)\).
Chúng ta hãy kiểm tra hai 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 số nguyên là \(1, 2, 4\) và \(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\) và \(6\), do đó
\(d(x) = 4\). Số \(y = 8\) có \(4\) ước số nguyên là \(1, 2, 4\) và \(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\)
Trong ví dụ thứ hai có \(6\) cặp cần tìm là \((9, 9), (9, 18), (9, 24), (18, 18), (18, 24)\) và \((24, 24)\).
Test 2
Input
25 9Output
6Scoring
- 20% số test: \(1 \le n \le 100\)
- 20% số test: \(1 \le n \le 600\)
- 20% số test: \(1 \le n \le 4000\)
- 20% số test: \(1 \le n \le 10^4\)
- 20% số test: Không có thêm ràng buộc
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.