Lập trình

Xem PDF
Tác giả:
huyhau6a2
Dạng bài
Điểm: 300 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Ông chủ của Hùng không thích Hùng. Vì vậy, ông đã sa thải anh ta. Hùng quyết định vào đại học và tham gia vào ACM thay vì tìm một công việc mới. Anh ấy muốn trở thành một thành viên của đội ACM. Để tham gia, anh được giao một số nhiệm vụ lập trình và một tuần để giải quyết chúng.

Hùng không phải là một lập trình viên giàu kinh nghiệm. Thật ra anh không phải là một lập trình viên. Vì vậy, anh không thể giải quyết chúng. Đó là lý do tại sao anh ấy yêu cầu bạn giúp anh ấy với những nhiệm vụ này. Một trong những nhiệm vụ này là như sau.
Một dãy số nguyên \(b\) độ dài \(k\) : \(b[1] ,  b[2] , ...,  b[k] (1 \le b[1]  \le   b[2]  \le ...  b[k]  \le   n )\) được gọi là tốt nếu mỗi số trước là ước của số sau. Tức \(b[i]\) là ước của \(b[i+1]\) với \(i=[1..k-1]\).

Cho \(n\) và \(k\), tìm số lượng dãy tốt độ dài \(k\). Vì câu trả lời có thể khá lớn, hãy lấy nó modulo \(1000000007(10^9+7)\) .

Input

  • Dòng đầu chứa \(q\) không quá \(100\)- số câu hỏi.
  • Dòng đầu tiên chứa hai số nguyên cách nhau không gian \(n,k(n*k \le 10^7)\) .

Output

Xuất ra một số nguyên duy nhất-số lượng các chuỗi tốt có độ dài \(k\) modulo \(1000000007(10^9+7)\)

Example

Test 1

Input 
1
3 2
Output 
5

Bình luận


  • 5
    huyhau6a2    8:34 p.m. 30 Tháng 12, 2021 ← chỉnh sửa 8

    Hint:

    • Đầu tiên ta giả xử xét số cuối trong mảng là i thì ta có thể cho được n/i số vào.
    • Ta sẽ tạo một mảng n số để xét số thứ i thì ta có thể đếm số cách có thể tạo được ở vị trí đầu là i.
    • Cách: Thiết lập mảng n phần tử đều có giá trị là 1.
    • Lặp k-1 lần, lặp từ 1 đến n, vị trí i=F(i)
    • F(i) là tổng tất cả phần tử có số hiệu chia hết cho \(i\). VD xét n=5 và tính F(2) thì ta tính tổng của phần tử 2 và 4, F(3) thì chỉ tính phần tử 3
    • VD test 4 3:
      --> 1 1 1 1
      --> 4 2 1 1
      --> 8 3 1 1
    • Cuối cùng ta chỉ cần tính tổng tất cả phần tử trên là bài toán đã được giải quyết
    • Cái cách này giống như truy vết từ cuối qua đầu cụ thể là ta tạo nhánh đuôi xong phát triển lên thành nhánh chính cho tiện tính tổng
    • Đừng nghĩ làm khó quá nha, cứ làm cách đơn giản nhất theo hint của mình nha
    • Lưu ý: chỉ nên làm mảng 1 chiều theo cách trên vì n và k<=\(10^5\) lận nha

    • 1
      hongquanyl1    10:03 p.m. 30 Tháng 12, 2021

      hay quá bạn nhỉ . Cho luôn vào hướng dẫn đi lào


      • 1
        huyhau6a2    7:05 a.m. 31 Tháng 12, 2021

        mong có người ac chứ mình dạo này ế lắm rồi huhu

    7 bình luận nữa