An interesting counting problem related to square product K
Xem PDF
Điểm:
400 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Given \(n, k (1 \leq k \leq n \leq 10^6)\), count the number of arrays \(a[]\) of size \(k\) satisfies:
- \(1 \leq a_1 < a_2 < \dots < a_k \leq n\).
- \(a_i \times a_j\) is a perfect square \(\forall 1 \leq i < j \leq k\).
Since the result can be large, output it under modulo \(10^9 + 7\).
Example
Test 1
Input
2 1Output
2Note
There are \(2\) satisfied array of size \(1\): {\(1\)}, {\(2\)}.
Test 2
Input
10 2Output
4Note
There are \(4\) satisfied array of size \(2\): {\(1, 4\)}, {\(1, 9\)}, {\(2, 8\)}, {\(4, 9\)}.
Test 3
Input
27 3Output
12Note
There are \(12\) satisfied array of size \(3\): {\(1, 4, 9\)}, {\(1, 4, 16\)}, {\(1, 4, 25\)}, {\(1, 9, 16\)}, {\(1, 9, 25\)}, {\(1, 16, 25\)}, {\(2, 8, 18\)}, {\(3, 12, 27\)}, {\(4, 9, 16\)}, {\(4, 9, 25\)}, {\(4, 16, 25\)}, {\(9, 16, 25\)}.
Bình luận
Translate is:Một bài toán đếm thú vị liên quan đến tích K bình phương
Được cho
N
,
k
(
1
≤
k
≤
N
≤
1
0
6
)
n,k(1<k<n<10
6
), đếm số mảng
Một
[
]
một [] kích thước
k
k thỏa mãn:
1
≤
Một
1
<
Một
2
<
⋯
<
Một
k
≤
N
1<a
1
<a
2
<⋯<a
k
≤n.
Một
Tôi
×
Một
j
Một
Tôi
×a
j
là một hình vuông hoàn hảo
∀
1
≤
Tôi
<
j
≤
k
∀1<i<j<k.
Vì kết quả có thể lớn nên xuất kết quả theo modulo
1
0
9
+
7
10
9
+7.
is gg dich
Sử dụng google dịch và làm
Use the google translate and do