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

-1

huyhau6a2 8:21 p.m. 8 Tháng 1, 2022

nà ní sao code của nguyenminhhai021009 và kingmasterpc1221321321331 giống nhau vậy, ảo thật đấy(không có ý nói các bạn copy nha, mình thắc mắc thôi)

2 phản hồi

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 phản hồi

0

ap 6:46 p.m. 31 Tháng 12, 2021

chắc để giống bài quân xe nhỉ:)

4 phản hồi

0

huyhau6a2 6:33 p.m. 31 Tháng 12, 2021

ai có vấn đề gì mình sẽ giải thích nha

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 phản hồi

0

huyhau6a2 7:10 p.m. 30 Tháng 12, 2021

nguồn: VDCODER

|| Hint
LQDOJ chúc bạn accepted and happy new year
||

1 phản hồi

0

huyhau6a2 6:08 p.m. 30 Tháng 12, 2021

ok chỉnh lại time rồi nha

0

huyhau6a2 5:59 p.m. 30 Tháng 12, 2021

bài này nhiều query nên mình cần chỉnh thời gian lại, không ac 1 hit trong 1 giây được đâu nha

1 phản hồi