Tóm tắt đề bài

Tìm số ~z~ lớn nhất sao cho ~z~ là số lập phương và ~z~ là ước của ~n!~. Hãy in ra ~z~ khi chia dư cho ~10^9 + 7~.

Giới hạn: ~n \le 10^5~.

Subtask 1. ~n \le 20~

Tính ~n!~, đặt ~y = \sqrt[3] z~, ta thấy ~y \le 3 \times 10^6~.

Duyệt ~y~, nếu ~n!~ chia hết cho ~y^3~ thì cập nhật vào kết quả.

Độ phức tạp: ~O~ (~t \times \sqrt[3] {n!}~)

Subtask 2. ~n \le 10^5~

Nếu ta gọi ~cnt_i~ là số thừa số ~i~ trong phân tích thừa số nguyên tố của ~n!~, ta thấy, thừa số ~i~ sẽ được đóng góp số lần là ~\lfloor \frac {cnt_i}{3} \rfloor~ ~\times 3~.

Lý do là bởi, vì ta muốn có ~z~ lớn nhất, nên ta sẽ lấy số thừa số tối đa có thể, nhưng vẫn phải đảm bảo chia hết cho ~3~ để thành số lập phương.

Vì vậy, ta sẽ phân tích ~n!~ ra thừa số nguyên tố. Ta sẽ phân tích từng thừa số từ ~1~ tới ~n~ thay vì tính hẳn ~n!~ rồi mới phân tích.

Về cách phân tích thừa số nguyên tố, các bạn có thể tham khảo tại VNOI Wiki.

Độ phức tạp: ~O~ (~t \times n \times \sqrt n~) hoặc ~O~ (~t \times n \times log~ ~n~) tùy vào phân tích thừa số nguyên tố bằng cách nào.