Nhận thấy "giá trị lắng đọng" của mảng luôn phải là ước của phần tử lớn nhất trong mảng ~(maxA)~ nên việc đầu tiên ta cần làm là duyệt qua toàn bộ các ước của ~maxA~. Khi đó, ta có thể chuyển bài toán về thành với mỗi ước ~x~, ta tìm xem có tồn tại cách chia mảng sao cho mỗi đoạn con liên tiếp đều có "giá trị tinh hoa" là bội của ~x~ và số đoạn con đó không ít hơn ~k~ hay không.

Gọi ~ans(l, r)~ là số đoạn chia tối đa ở trên đoạn ~[l, r]~ của mảng ~a~. Ta giả sử trên đoạn ~[l, r]~ có cực đại nằm tại vị trí ~pivot~:

• Nếu ~a[pivot]~ chia hết cho ~x~: ta tham lam lấy phần tử ~a[pivot]~ làm ~1~ đoạn con có độ dài bằng ~1~ và chia tiếp ở hai đầu của mảng ~\rightarrow~ ~ans(l, r) = ans(l, pivot-1) + 1 + ans(pivot+1, r)~

• Nếu ~a[pivot]~ không là bội của ~x~:

  • Trường hợp ~l > 1~: Ta thấy khi đó sẽ có thể tồn tại một phần tử nào ở bên trái đoạn con thỏa mãn ~a[i] \geq a[pivot]~ và ~a[i]~ là bội của ~x~. Khi đó, ta chỉ cần "sáp nhập" các phần tử bên trái ~pivot~ và chính ~a[pivot]~ vào đoạn con chứa ~a[i]~ đó và chia tiếp các đoạn con còn lại ~\rightarrow~ ~ans(l, r) = ans(pivot+1, r)~

  • Trường hợp ~r < n~: Tương tự trường hợp ~l > 1~ ~(ans(l, r) = ans(l, pivot-1))~

  • Vậy kết luận khi này ~ans(l, r) = max(ans(l, pivot-1), ans(pivot+1, r))~

Việc còn lại chỉ là tìm cách để truy xuất cực đại của mỗi đoạn con ~[l, r]~ nhanh nhất có thể. Khi này, việc tìm cực đại của mỗi đoạn con hoàn toàn tương tự bài toán RMQ cổ điển (có thể giải bằng các cấu trúc dữ liệu như Sparse Table, Segment Tree…)

ĐPT: ~O(n \log n+n \cdot \sigma_0(maxA))~ với ~\sigma_0(n)~ là hàm đếm số ước nguyên dương phân biệt của ~n~.