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


  • 4
    huyhau6a2    8:56 p.m. 31 Tháng 12, 2021 ← chỉnh sửa 9
    • alo mình thấy vẫn chưa ai ac nên mình xin gợi ý thêm nha: từ phần tử n/2 tới n trở đi tất cả phần tử đó luôn bằng 1 do F(i) chỉ có i là số duy nhất chia hết cho i. VD: n=5 thì các phần tử 3->5 là số hiệu 1 hết, n=10 thì các phần tử 6->10 luôn là số 1. Vậy ta có thể chặt 1/2 time cho phần cộng
    • Một lưu ý khác là hàm F(i) tính tổng tất cả phần tử có số hiệu chia hết cho i. Các bạn có thể xem lại hint với ví dụ để sửa code nha bạn
    • Thêm nữa các bạn có thể giảm phần mod bằng cách : VD hàm F(i) thì tính long long xong return giá trị kết quả mod sau cũng được. Hoặc với đoạn tính tổng các bạn cũng co thể tính tổng tất cả phần tử trước, lưu long long xong mới xuất kết quả mod, làm vậy cũng có thể giảm time cho code
    • Các bạn chưa ac do tle hoặc wa có thể dựa vào hint này để sửa lại code cho ac dễ hơn
    • Nếu có cách nào chặt time tối ưu hơn nữa các bạn có thể nhắn gợi ý cho các bạn khác nữa nha

    • 2
      nguyendanghau2006    10:45 p.m. 31 Tháng 12, 2021

      tui...... vẫn chưa hiểu được test đề :((


      • 2
        VoBaThongL921    9:43 p.m. 31 Tháng 12, 2021

        Yay thanks bạn nha 😃 ko ngờ cái phép mod mà trong c++ nó tính lâu z, sau này mình hạn chế


        • 2
          huyhau6a2    7:22 a.m. 1 Tháng 1, 2022

          Cái này giảm được khoảng một nửa số phép tính nên giảm được kha khá thời gian đó


          • 1
            nguyendanghau2006    10:48 p.m. 31 Tháng 12, 2021

            giải thích test đề giùm tui đi :((

        7 bình luận nữa