Lời giải chi tiết

Ý tưởng: Trước hết, cần kiểm tra số \(n\) có bao nhiêu ước. Nếu số ước của \(n\) nhỏ hơn \(k\) in ra -1. Nếu ngược lại, mỗi ước thứ \(i\) của số \(n\) ta kiểm tra xem ước thứ \(i\) từ nhỏ tới lớn hoặc ước thứ \(i\) từ lớn về nhỏ, xem có bằng \(k\) hay không. Khi xảy ra trường hợp bằng, in ra vị số đó tùy theo vị trí xét và kết thúc chương trình.

Chú ý: Nếu chỉ dùng vòng lặp thông thường duyệt \(i\) từ 1 tới \(n\), ta sẽ bị lỗi chạy quá thời gian (TLE) do số \(n\) tương đối lớn. Vì vậy ta chỉ nên duyệt \(i\) từ 1 tới \(\sqrt{n}\).

Các bước giải:

• Bước 1: Khai báo và nhập vào hai số nguyên dương \(n, k\).
• Bước 2: Khai báo biến count \(= 0\) biểu thị số ước của \(n\).
• Bước 3: Sử dụng vòng lặp để duyệt các số \(i\) từ 1 tới \(\sqrt{n}\). Nếu \(n\) chia hết cho \(i\) ta cộng count thêm 2 do thêm cả \(n/i\) cũng chia hết cho \(n\). Lưu ý tới trường hợp số chính phương. Lúc này khi duyệt tới \(\sqrt{n}\) ta sẽ có \(i = n/i\). Vì vậy nếu gặp trường hợp này ta cần trừ count đi 1.
• Bước 4: Sau khi đếm được số ước của \(n\), nếu count \(< k\) ta trả kết quả về \(-1\) và kết thúc chương trình. Ngược lại ta tiếp tục với bước tiếp theo.
• Bước 5: Tạo biến dem \(=0\) biểu thị vị trí ước đang duyệt tới của \(n\).
• Bước 6: Tiếp tục duyệt các số \(i\) từ 1 tới \(\sqrt{n}\). Nếu \(i\) là ước của \(n\), ta cộng dem thêm 1, sau đó ta kiểm tra ước ở vị trí thứ dem hiện tại và count \(-\) dem \(+1\). Nếu dem \(= k\) ta in ra kết quả là \(i\). Còn nếu count \(-\) dem \(+1 = k\) ta in ra kết quả là \(n/i\). Sau đó kết thúc chương trình.

Độ phức tạp của thuật toán này: \(O(\sqrt{n})\).

Đăng ký khóa học: https://www.facebook.com/clblaptrinhfullhouse

SĐT liên hệ: 0372229686

Youtube: CLB Lập Trình Full House

Fullhouse dev đồng hành trên từng dòng code