Lập trình

Tác giả:

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

Bình luận

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
4
Phản hồi Chia sẻ

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

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

2
Phản hồi Chia sẻ

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
Phản hồi Chia sẻ

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 đó

2
Phản hồi Chia sẻ

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

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

1
Phản hồi Chia sẻ

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

Có 5 dãy tốt là 1 1; 1 2; 1 3; 2 2; 3 3

3
Phản hồi Chia sẻ

nguyendanghau2006 • 12:25 p.m. 1 Tháng 1, 2022 •

Hmm 🤔🤔🤔🤔

1
Phản hồi Chia sẻ

huyhau6a2 • 12:29 p.m. 1 Tháng 1, 2022 •

?????

1
Phản hồi Chia sẻ

7 bình luận nữa