Tóm tắt đề bài

Cho mảng \(A\) gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Với mỗi vị trí \(i\), hãy tìm vị trí nhỏ nhất \(j>i\) sao cho \(a_j\) có nhiều ước dương hơn \(a_i\). In ra \(a_j\) tương ứng; nếu không tồn tại thì in ra \(-1\).

Phân tích

• Ràng buộc: \(n \le 2\cdot 10^5\), \(a_i \le 10^9\).
• Bài toán gồm 2 phần:
  • Tính số ước \(d(x)\) cho từng phần tử.
  • Với dãy \(d[i]=d(a_i)\), tìm phần tử gần nhất bên phải có giá trị lớn hơn (Next Greater Element) theo tiêu chí \(d\).
• Tính số ước của một số \(x\):
  • Phân tích \(x = \prod p_k^{e_k}\) thì số ước:

• Vì \(a_i \le 10^9\), ta chỉ cần các số nguyên tố \(\le \sqrt{\max(a_i)}\) để thử chia.
• Code AC sàng nguyên tố đến \(\sqrt{\max A}\) và tính \(d(a_i)\) bằng phân tích thừa số theo danh sách prime.

Hướng giải quyết

Nhận xét

• Sau khi có mảng \(d[i]\), yêu cầu của đề trở thành:
  • Với mỗi \(i\), tìm chỉ số nhỏ nhất \(j>i\) sao cho \(d[j] > d[i]\), rồi in ra \(a[j]\).
• Đây là bài toán kinh điển Next Greater Element (NGE), giải bằng stack đơn điệu trong \(O(n)\):
  • Duyệt từ phải sang trái.
  • Stack lưu các chỉ số ứng viên bên phải, đảm bảo \(d\) giảm dần từ đáy lên đỉnh.
  • Khi xử lý \(i\), loại bỏ mọi chỉ số ở đỉnh có \(d[\text{top}] \le d[i]\) vì chúng không thể là “lớn hơn” cho \(i\) và cũng không hữu ích cho các phần tử bên trái.

Thuật toán

1. Đọc \(n\) và mảng \(a\); lấy \(maxA = \max(a_i)\).
2. Sàng Eratosthenes tạo danh sách nguyên tố primes đến \(\lfloor \sqrt{maxA} \rfloor + 1\).
3. Với mỗi \(a_i\), tính \(d[i]\) bằng phân tích thừa số:
   • Với mỗi prime \(p\):
     • Nếu \(p^2 > a_i\) thì dừng.
     • Đếm số lần chia hết \(p\) (số mũ \(cnt\)), cập nhật \(res \leftarrow res \cdot (cnt+1)\).
   • Nếu sau cùng còn \(a_i > 1\) thì nhân thêm \(2\) (một thừa số nguyên tố mũ \(1\)).
4. Tìm NGE theo \(d\):
   • Khởi tạo stack rỗng st (lưu chỉ số).
   • Duyệt \(i\) từ \(n-1\) xuống \(0\):
     • Trong khi st không rỗng và \(d[st.top] \le d[i]\) thì pop.
     • Nếu st còn phần tử, đáp án tại \(i\) là \(a[st.top]\), ngược lại là \(-1\).
     • Push \(i\) vào stack.
5. In mảng đáp án.

Pitfall thường gặp

• Khi tìm “nhiều ước hơn”, điều kiện là strict: cần \(d[j] > d[i]\), vì vậy khi pop phải dùng \(\le\) (không phải <).
• Tính số ước phải dùng kiểu đủ lớn khi kiểm tra \(p^2\) (trong code dùng (long long)p * p).

Độ phức tạp

• Sàng nguyên tố: \(O(\sqrt{maxA}\log\log \sqrt{maxA})\).
• Tính số ước: xấp xỉ \(O\big(n \cdot \pi(\sqrt{maxA})\big)\) trong trường hợp xấu, nhưng thực tế nhanh do dừng sớm khi \(p^2 > n\) và sau khi chia số giảm mạnh.
• NGE bằng stack: \(O(n)\).
• Bộ nhớ: \(O(n)\) cho các mảng và stack.

Code tham khảo

Tự code là chân lý