Thông tin
Sau đây là lời giải của Đề 4 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)
Để không tồn tại số nguyên dương khác là ước chung của và , và chỉ được phép có ước chung là và tối đa một số nguyên tố (có thể có hoặc không).
Duyệt mọi số , sau đó duyệt qua từng ước của , và đếm số lượng ước chung của và .
Nếu số lượng ước chung khác lớn hơn hoặc bằng , cặp số này không phải là cặp số không tương đồng. Ngược lại, ta ghi nhận thêm một cặp số không tương đồng.
Độ phức tạp thời gian: .
Nhận xét
Mọi uớc chung của và đều là ước của .
Như vậy, để kiểm tra hai số có nhiều hơn ước chung khác hay không, ta chỉ cần kiểm tra xem có không quá ước khác hay không.
Trường hợp trên chỉ xảy ra khi:
Như vậy, để giải bài này, ta thực hiện kiểm tra có phải là số nguyên tố hay không với mọi .
Chú ý điều kiện
Độ phức tạp thời gian: .
là chi phí để tính bằng hàm
__gcd()
.
là chi phí để kiểm tra tính nguyên tố của .
Nhận xét
Dễ dàng quan sất thấy, nên chọn đĩa có độ bền lớn nhất đặt làm đáy vì đĩa nằm ở dưới cùng sẽ phải chịu tải nhiều nhất.
Tổng quát hơn, đĩa càng nằm sâu ở dưới sẽ càng có độ bền lớn, tức là độ bền của đĩa giảm dần từ dưới đáy lên đỉnh.
Như vậy, ta sắp xếp lại các chiếc đĩa theo độ bền giảm dần và lần lượt xếp những chiếc đĩa từ đầu dãy tạo thành một tháp.
Trong lúc xây tháp, ta kiểm tra xem có đĩa nào bị quá tải hay không bằng cách duy trì biến là độ bền còn lại của đĩa có độ bền nhỏ nhất. Một khi độ bền về , ta không thể đặt thêm đĩa được nữa.
Độ phức tạp thời gian: .
Độ phức tạp của hàm
sort()
.
Áp dụng quy hoạch động.
Độ phức tạp .
Duyệt bảng, tính giá trị ở từng ô và đưa vào một mảng. Sau đó sắp xếp lại và đưa ra số trung vị của dãy.
Độ phức tạp thời gian: .
Ta cần sắp xếp một dãy có phần tử.
Nhận xét
Gọi là số lượng số nhỏ hơn hoặc bằng trong bảng.
Đáp án của bài chính là số nhỏ nhất thỏa . Vì tăng thì cũng tăng, nên dễ dàng tính được đáp án bằng tìm kiếm nhị phân trên tập đáp án.
Giá trị nhỏ nhất trong bảng nhân là và giá trị lớn nhất là , đây cũng là khoảng đáp án mà ta sẽ thực hiện tìm kiếm nhị phân.
Để tính với một số bất kỳ, ta thực hiện như sau:
Các giá trị ở hàng có dạng với .
Mà là số nguyên, do đó ta lấy làm tròn xuống.
Khi tính , chú ý chúng ta chỉ lấy số trong phạm vi của bảng, tức là tối đa chỉ có số. Vậy số lượng số nhỏ hơn hoặc bằng trong hàng là .
Độ phức tạp thời gian: