An interesting counting problem related to square product K

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
SPyofgame , SPectiar2k
Dạng bài
Đ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 1
Output 
2
Note

There are \(2\) satisfied array of size \(1\): {\(1\)}, {\(2\)}.

Test 2

Input 
10 2
Output 
4
Note

There are \(4\) satisfied array of size \(2\): {\(1, 4\)}, {\(1, 9\)}, {\(2, 8\)}, {\(4, 9\)}.

Test 3

Input 
27 3
Output 
12
Note

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


  • 0
    vietnammuonnam_mvn    6:25 p.m. 30 Tháng 7, 2024

    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.

      • 3 bình luận nữa