Thông tin
Sau đây là lời giải của Đề 3 trong chuỗi đề ôn tập TS10 & THTB 2025.
Bạn đọc có thể nộp và chấm bài TẠI ĐÂY
Chuẩn bị bởi team Logica, thuộc khuôn khổ dự án The Algitect (ALGI Project)
Đếm ước
Để đếm số lượng ước của một số , ta thực hiện:
Chú ý trường hợp .
Duyệt các số từ đến và đếm số lượng số có ước.
Độ phức tạp thời gian:
Cải tiến đếm ước
Áp dụng kĩ thuật sàng ước:
Thao tác trên mất chi phí .
.
Độ phức tạp thời gian:
Cải tiến đếm ước
Với một số , trong đó:
Số ước của n là:
Để biểu thức trên bằng , ta chỉ cần xét hai trường hợp:
Như vậy, bài toán trở thành:
Đếm số lượng số nguyên dương có dạng và .
Nói cách khác, đáp án chính là số lượng số nguyên tố mũ cộng với số lượng bình phương tích của hai số nguyên tố khác nhau sao cho chúng có giá trị nằm trong đoạn
Đếm số lượng số nguyên tố mũ 8
Duyệt từng số nguyên bằng vòng lặp, kiểm tra nếu là số nguyên tố và thì là một số thỏa mãn đề bài.
Độ phức tạp thời gian: .
Lưu ý, cần phải thoát ra khỏi vòng lặp khi .
Đếm số lượng bình phương của tích hai số nguyên tố khác nhau
Ta có:
Đề bài cho , như vậy ta chỉ cần xét các số nguyên tố nhỏ hơn hoặc bằng .
Từ đến chỉ có số nguyên tố. Ta lấy ra trước các số nguyên tố này, sau đó chạy hai vòng lặp lồng nhau lấy ra mọi cặp số nguyên tố.
Độ phức tạp thời gian: .
Độ phức tạp thời gian của cả bài là tổng độ phức tạp thời gian của hai thao tác.
Nhận xét
Chaien luôn lấy rương có nhiều xu nhất, để đảm bảo số xu bỏ vào sẽ không phí, Suneo sẽ phải bỏ vào rương nhiều xu nhất.
Ta làm như sau:
Độ phức tạp thời gian:
là số thao tác để sắp xếp mảng bằng hàm
sort()
.
Nhận xét:
Dựa vào việc nút bấm sau phải có số điểm nhỏ hơn nút đã bấm trước đó, ta có:
Tại một vị trí , sẽ không cần phải triệu hồi rô-bốt (tức là ô này đảm bảo sẽ được bấm mà tại đó không cần triệu hồi rô-bốt) khi và chỉ khi:
Vì từ những ô kế được nhắc đến ở trên, rô-bốt có thể di chuyển sang ô và bấm nút.
Như vây, chỉ cần phải triệu hồi một rô-bốt ở vị trí bất kỳ trên một đoạn liên tiếp mà thỏa mãn:
Ví dụ: , có đoạn thỏa mãn yêu cầu trên.
Tta chỉ cần triệu hồi rô-bốt ở trong ô đó và sẽ luôn có cách di chuyển rô-bốt qua các ô xung quanh để bấm nút theo thứ tự điểm giảm dần.
Áp dụng kĩ thuật hai con trỏ:
Độ phức tạp thời gian: .
Nhận xét
Một hình vuông kích thước cạnh có góc trái trên là ô thì sẽ có góc phải dưới là ô .
Để kiểm tra một hình vuông có gồm toàn số hay không, ta duyệt qua các ô trong đó để tính tổng các giá trị, tổng này phải bằng .
Thử mọi kích thước có thể của hình vuông từ lớn đến bé, nếu có tồn tại hình vuông kích thước thì đáp án là và số lượng hình vuông có kích thước .
Độ phức tạp thời gian:
Đây là độ phức tạp lý thuyết - độ phức tạp thực tế sẽ nhỏ hơn nhiều, đủ để chạy với giới hạn .
Nhận xét
Có thể tạo ra hình vuông toàn cạnh có góc phải dưới là ô khi và chỉ khi và cũng có thể tạo ra ba hình vuông toàn cạnh có góc phải dưới là ô .
Áp dụng quy hoạch động:
nếu thỏa mãn đồng thời:
- và và .
Độ phức tạp thời gian: